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

你的益达

发布于 2020-08-05 06:45:10

1.1K00

代码可运行

文章被收录于专栏：阿伟的个人博客阿伟的个人博客

运行总次数：0

代码可运行

问题描述：

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决方案

该问题和之前剑指offer中那个寻找逆序对的问题类似。采用归并排序的做法解决，具体做法如下：

首先新建一个类Node，用于封装每个元素的值及其原始下标，将原始数组转化为Node数组记做arr。

对arr以其存储的值为key进行归并排序，排序过程中需注意的是应从后往前排。若此时两端位置为left，right，其中间元素下标记做mid，并的过程中i为前半端当前位置初值为mid，j为后段当前位置初值为right。若此时arr[i] > arr[j] 我们可以知道arr从mid + 1到 j 的位置所有值都比arr[i]小，就把j - mid加到arr[i]所对应的下标上去。如此直到归并排序结束即可。

代码如下：

class Solution {
    public static class Node{
        int index;
        int val;
        public Node(int index, int val){
            this.index = index;
            this.val = val;
        }
    }
    public List<Integer> countSmaller(int[] nums) {
        int N = nums.length;
        List<Integer> result = new ArrayList<>(N);
        Node[] arr = new Node[N];
        for(int i = 0; i < N; i++){
            result.add(0);
            arr[i] = new Node(i, nums[i]);
        }
        merge(0, N - 1, arr, result);
        return result;

    }
    public void merge(int left, int right, Node[] arr, List<Integer> result){
        if(left >= right){
            return;
        }
        int mid = (left + right) / 2;
        merge(left, mid, arr, result);
        merge(mid + 1, right, arr, result);
        List<Node> temp = new ArrayList<>(right - left + 1);
        // i为前半段结尾位置， j为后半段结尾位置
        int i = mid;
        int j = right;
        while(i >= left && j > mid){
            if(arr[i].val > arr[j].val){ // 说明j之前的所有元素都比其小
                result.set(arr[i].index, result.get(arr[i].index) + j - mid);
                temp.add(arr[i--]);
            }else{
                temp.add(arr[j--]);
            }
        }
        while(i >= left){
            temp.add(arr[i--]);
        }
        while(j > mid){
            temp.add(arr[j--]);
        }
        int k = 0;
        while(right >= left){
            arr[right--] = temp.get(k++);
        }
    }
}