题目

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

内容

给定一个整数数组 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 个更小的元素.

题解

计算右侧小于当前元素的个数，也就是我们可以对 第i位的num右侧的数列进行排序 然后插入nums[i] 插入位置就是 右侧小于当前元素的个数，在寻找插入位置时直接循环查找会超时，所以我们在这部分做二分查找 所以最差时间是logn! 而直接循环查找的话最差 1/2+1/2n^2*.

代码

 public List<Integer> countSmaller(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        if (nums.length == 0)
            return new ArrayList<>();
        int len = nums.length;

        Integer[] maxn = new Integer[nums.length];
        maxn[len - 1] = 0;
        int j = 0;
        list.add(nums[len - 1]);
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] > list.get(list.size() - 1)) {
                maxn[i] = list.size();
                list.add(nums[i]);
            } else {
                int l = 0;
                int r = list.size() - 1;
                while (l < r) {
                    int m = (l + r) / 2;
                    if (nums[i] > list.get(m)) {
                        l = m + 1;
                    } else {
                        r = m;
                    }
                }
                list.add(r, nums[i]);
                maxn[i] = r;
            }
        }
        return Arrays.asList(maxn);
    }

结果

image.png