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

难度: 🌕🌕🌕

问题描述

---

解法

class Solution {
    int[] indArr;
    int[] cArr;
    public List<Integer> countSmaller(int[] nums) {
        // 思路：
        // 归并排序 
        // 在 merge() 的过程中统计各个下标处的元素个数
        // 由于 merge() 过程会修改元素位置，导致元素所在下标发生改变，因此还需记录排序好的元素对应的初始下标
        // 如何记录？
        // 若是所有元素均不重复，可以借助 HashMap<val, index> 的形式记录
        // 但是题意未标明，说明元素有重复值，此时 map 无法记录，因此采用 数组 形式，下标表示初始下标，值表示排序后的下标
        int len = nums.length;
        indArr = new int[len]; // 记录 初始下标 - 排序好后下标 关系
        cArr = new int[len]; // 记录 indArr[i] - count 关系
        for(int i = 0; i < len; i ++) {
            indArr[i] = i;
        }
        mySol(nums, 0, len - 1);
        
        int[] res = new int[len]; // 记录 初始下标 - count 关系
        for(int i = 0; i < len; i ++) {
            int finalIndex = indArr[i]; // 初始下标 i - 当前 nums 下标
            res[finalIndex] = cArr[i];
        }
        List<Integer> ans = new ArrayList<>();
        for(int i = 0; i < len; i ++) {
            ans.add(res[i]);
        }
        return ans;
    }

    private void mySol(int[] nums, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        mySol(nums, left, mid);
        mySol(nums, mid + 1, right);
        // 判断左右两个区间是否已经是递增的，若是，则无需排序，直接拼接就是排好序的数组，进而也没有 count
        if(nums[mid] <= nums[mid + 1]) {
            // 前一个数组的 max <= 后一个数组的 min
        } else {
            // 需要排序，且必存在某个下标处需要更新 count
            merge(nums, left, mid, right);
        }
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int i = left;
        int j = mid + 1; // 左右数组指针
        int[] newArr = new int[right - left + 1]; // 存储新的排序好的数组
        int[] newIndArr = new int[right - left + 1]; // 存储新的排序好的下标对应关系
        int[] newCArr = new int[right - left + 1]; // 存储新的 count 关系
        int index = 0;

        while(i <= mid && j <= right) {
            // 理论上，当 [i] > [j] 时，{[i], [i + 1] ... [mid]} > [j]，集合中所有下标处均需 count ++
            // 但是这样就造成了从 [i] --> [mid] 的遍历
            // 如果换一个角度：
            // [i] < [j] 时，[i] > {[mid + 1], ..., [j - 1]} 可直接计算出 [i] 对应的 count += j - 1 - mid
            // [i] == [j] 时，取 [i], i ++，此时仍然满足 [i] > {[mid + 1], ..., [j - 1]}
            if(nums[i] <= nums[j]) {
                // 统计 [i] 下标处的 count，将 [i] 放入 newArr[]
                cArr[i] += j - 1 - mid; // 先修改 count，再放到新的 count 数组对应位置
                newCArr[index] = cArr[i];
                newIndArr[index] = indArr[i];
                newArr[index] = nums[i];
                i ++;
                index ++;
            } else {
                newCArr[index] = cArr[j];
                newIndArr[index] = indArr[j];
                newArr[index] = nums[j];
                j ++;
                index ++;
            }
        }

        while(i <= mid) {
            // {[i], ..., [mid]} 均比 {[mid + 1], ..., [right]} 大
            cArr[i] += right - mid;
            newCArr[index] = cArr[i];
            newIndArr[index] = indArr[i];
            newArr[index] = nums[i];
            i ++;
            index ++;
        }
        while(j <= right) {
            // {[j], ..., [right]} 均比 左侧区间大，即不存在 count
            newCArr[index] = cArr[j];
            newIndArr[index]  = indArr[j];
            newArr[index] = nums[j];
            j ++;
            index ++;
        }

        // 替换原数组
        for(int m = 0; m < newArr.length; m ++) {
            nums[m + left] = newArr[m];
            indArr[m + left] = newIndArr[m];
            cArr[m + left] = newCArr[m];
        }
        // System.out.println(" ===============  ");
        // System.out.println(Arrays.toString(indArr) + "  " + Arrays.toString(nums) + "  " + Arrays.toString(cArr));
    }
}

---

输出