Hard | LeetCode 315. 计算右侧小于当前元素的个数 | 归并排序

标签：off   数组中的逆序对   示例   位置   number   for   提示   一个   targe   

315. 计算右侧小于当前元素的个数

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

提示：

• 0
• -10^4

解题思路

方法一： 归并排序

此题要求, 某个数右边比当前元素小的元素的个数, 也就是找逆序对。不过逆序对还需要在第一个元素的位置进行计数。找逆序对与 Hard | 剑指 Offer 51. 数组中的逆序对 | 归并排序 类似, 要针对每个下标进行计数, 使用一个索引数组即可。

索引数组：新建一个数组保存源数组中所有元素的下标。针对源数组中所有元素的位置变动, 源数组不做任何改动, 只变动索引数组。在需要进行大小比较时, 以索引数组的的某个值, 作为源数组的下标, 可以获得真正的值。

然后题目是要求某个数里, 从右边找比当前元素小的个数。

在 Hard | 剑指 Offer 51. 数组中的逆序对 | 归并排序 我们知道, 在找两个有序数组的逆序对时(假设为[[A],[B]]), 从左往右归并, 若ra > rb, 则说明形成了逆序对, 则ra后边的元素全部比rb 大。也就是可以得到数组里某个数组, 左边比当前元素大的部分。而要一次找出右边比当前元素小的部分, 则从左往右归并是无法一次找出的。

解决办法是：从右往左归并, 通过这种归并顺序, 就可以一次找出右边比当前元素小的个数。

public List countSmaller(int[] nums) {
    // index 作为索引数组, 排序时, 需要对索引数组进行排序
    // 在排序过程当中比较的对象是索引数组的值作为原数组下标的值
    int[] index = new int[nums.length];
    for (int i = 1; i  resList = new ArrayList(res.length);
    for (int re : res) {
        resList.add(re);
    }
    return resList;
}

public void mergeSortCore(int[] nums, int[] index,  int left, int right, int[] temp, int[] res) {
    if (left >= right) {
        return;
    }

    // 先将数组切分成两半, 递归的归并这两个一半的数组
    int mid = (left + right) >> 1;
    mergeSortCore(nums, index, left, mid, temp, res);
    mergeSortCore(nums, index, mid + 1, right, temp, res);
    // 两个一半的数组归并完成之后, 保存nums数组的[left, right]部分到temp作为归并的辅助数组
    for (int i = left; i = left && bPtr > mid) {
        if (nums[temp[aPtr]] 

Hard | LeetCode 315. 计算右侧小于当前元素的个数 | 归并排序

标签：off   数组中的逆序对   示例   位置   number   for   提示   一个   targe   

原文地址：https://www.cnblogs.com/chenrj97/p/14654214.html