题目描述

blablabla

样例

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        // 从右向左遍历，对于前面的元素来说并不关心后面元素的排列。所以后面元素可以从小到大排序
        // 有序后找小于当前元素x的数的个数就可以使用二分法快速查找,找到t要插入的位置i，则比t小的数有i个。
        Integer[] res = new Integer[nums.length];
        List<Integer> tmp = new ArrayList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            int idx = binary(tmp, nums[i]);
            tmp.add(idx, nums[i]);
            res[i] = idx;
        }
        return Arrays.asList(res);
    }

    int binary(List<Integer> list, int t) {
        int l = 0; 
        int r = list.size();
        while (l < r) {
            int mid = l + r >> 1;
            if (list.get(mid) >= t) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}