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

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

难度困难581

给定一个整数数组 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 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

归并排序

因为归并后的数字的顺序发生了变化，在计算贡献的时候如果不保存当前数字的原先的位置，那么在计算的过程中会加到别的数字上面去，导致结果不再正确，此时就需要在归并的时候处理原来的index，防止将贡献加到不对的地方。

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        temp = new int[n];
        ans = new int[n];
        index = new int[n];
        tempIndex = new int[n];

        for(int i = 0; i < n; i++){
            index[i] = i;
        }

        mergeCount(nums,0,n-1);

        List<Integer> res = new ArrayList<Integer>(ans.length);
        for(int i=0;i<n;i++){
            res.add(ans[i]);
        }
        return res;
    }

    int[] temp;
    int[] ans;
    int[] index;
    int[] tempIndex;
    public void mergeCount(int []nums,int l,int r){
        if(l >= r)return;

        int m = l + (r - l) / 2;
        mergeCount(nums,l,m);
        mergeCount(nums,m+1,r);

        int i = l , j = m + 1;
        int cnt = 0;
        while(i <= m && j <= r){
            if(nums[i] <= nums[j]){
                temp[cnt] = nums[i];
                tempIndex[cnt] = index[i];
                ans[index[i]] += j - m - 1;
                cnt++;
                i++;
            }else{
                temp[cnt] = nums[j];
                tempIndex[cnt] = index[j];
                cnt++;
                j++;
            }
        }
        while(i <= m){
            temp[cnt] = nums[i];
            tempIndex[cnt] = index[i];
            ans[index[i]] += j - m - 1;
            cnt++;
            i++;
        }
        while(j <= r){
            temp[cnt] = nums[j];
            tempIndex[cnt] = index[j];
            cnt++;
            j++;
        }

        for(int k=0;k < r - l + 1; k++){
            nums[l+k] = temp[k];
            index[l+k] = tempIndex[k];
        }
    }
}

赏

谢谢你请我吃糖果

微信