必刷算法100题之计算右侧小于当前元素的个数

 题目链接

315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）

题目解析

计算数组里面所有元素右侧比它小的数的个数, 并且组成一个数组,进行返回

算法原理

归并解法(分治)

当前元素的后面, 有多少个比我小(降序)

我们要找到第一比左边小的元素, 这样就可以找到一堆比左边小的元素: right - cur2+1

nums[cur1]对应的位置,里面的ret[原始下标]+=right-cur2+1

我们算出cur1右边有多少个比它小的时候, 就需要把计算出来的个数放进结果数组ret里面

此时我们就需要找到nums数组中当前元素原始下标,然后把数记上 , 此时我们要解决的就是,怎么找到原始的下标, 因为每次归并, nums数组的元素位置会发生改变.

我们使用一个数组的每一个元素来一一对应记录nums每个元素的原始下标

然后在每一次归并排序,排完后,下标也跟着变(绑定移动)

细节问题, 在创建辅助数组进行合并的时候, 需要创建俩个辅助数组, 一个给nums,一个给index,因为俩个数组是同步改变的

代码编写

class Solution {
    int[] ret;//保存计算出来的每个元素右侧更小的数量
    int[] index;//用来保存每个元素对应的原始下标
    int[] tepRet;//用来保存每一段区间排好序的临时数组
    int[] tepIndex;//用来保存每次归并后元素下标的变化

    public void mergeSort(int[] nums, int left, int right) {
        //递归的终点
        if (left >= right) {
            return;
        }
        //计算中间下标
        int mid = (right - left) / 2 + left;
        //递归左边
        mergeSort(nums, left, mid);
        //递归右边
        mergeSort(nums, mid + 1, right);
        int cur1 = left;//左区间起始位置
        int cur2 = mid + 1;//右区间起始位置
        int i = 0;
        //归并(降序)
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) {
                //局部排序数组元素,把大的放前面
                tepRet[i] = nums[cur2];
                //更新下标
                tepIndex[i++] = index[cur2++];
            } else {
                //升序就说明找到了一堆
                ret[index[cur1]] += right - cur2 + 1;
                tepRet[i] = nums[cur1];
                tepIndex[i++] = index[cur1++];
            }
        }
        //处理剩余元素
        while (cur1 <= mid) {
            tepRet[i] = nums[cur1];
            tepIndex[i++] = index[cur1++];
        }
        while (cur2 <= right) {
            tepRet[i] = nums[cur2];
            tepIndex[i++] = index[cur2++];
        }
        //还原
        for (int j = left; j <= right; j++) {
            nums[j] = tepRet[j - left];
            index[j] = tepIndex[j - left];
        }
    }

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        ret = new int[n];
        index = new int[n];
        tepRet = new int[n];
        tepIndex = new int[n];
        //记录下原始的下标
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        //归并来进行处理
        mergeSort(nums, 0, n - 1);
        ArrayList<Integer> list = new ArrayList<>();
        for (int x : ret) {
            list.add(x);
        }
        return list;

    }
}

注意: 1> 我们在进行递归的时候,不仅要保存当前数组值在排序后的的临时数组, 也要保存下标的临时数组

        2> 多思考为什么此时我们临时数组是直接赋值大小都为n,而不是像之前是一个区间数组