题目

(https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/)
给定一个整数数组 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 个更小的元素.
在真实的面试中遇到过这道题？

分析

二话不说使用暴力解题（双重遍历）。超时。
嗯，要对代码进行优化
这道题从后往前遍历会比较清楚明了。优化点主要在sorted这个数列。这个sorted实现了对遍历到当前i之后的数据进行排序插入、然后就可以使用二分法进行获取当前大于或者等于nums[i]的第一个位置。这个位置就是当前值的逆序数

代码

 class Solution {
        public List<Integer> countSmaller(int[] nums) {
            Integer[] res = new Integer[nums.length];
            //sort其实是关键。sort的目的是 对i后面的元素进行从小到大的排序。
            // 每次插入新的数值，前面有几个数就是这个数值现在的逆序数
            List<Integer> sorted = new ArrayList<>(nums.length);
            int length = nums.length;
            // 从后往前计算
            for (int i = length - 1; i >= 0; i--) {
                int idx = binarySearch(sorted, nums[i]);
                res[i] = idx;
                //实现对sorted的排序。
                sorted.add(idx, nums[i]);
            }

            return Arrays.asList(res);
        }
        // 使用二分法。找大于或等于key的第一个位置
        private int binarySearch(List<Integer> list, int key) {
            int l = 0;
            int r = list.size();
            while(l<r){
                 int m = l + (r - l) / 2;
        if (list.get(m) < key) {
            l = m + 1;
        } else {
                r = m;
        } 
            }
            return l;
        }
    }

结果

image.png