題目

(https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/)
給定一個整數(shù)數(shù)組 nums，按要求返回一個新數(shù)組 counts。數(shù)組 counts 有該性質(zhì)： counts[i] 的值是 nums[i] 右側(cè)小于 nums[i] 的元素的數(shù)量。

示例:

輸入: [5,2,6,1]
輸出: [2,1,1,0]
解釋:
5 的右側(cè)有 2 個更小的元素 (2 和 1).
2 的右側(cè)僅有 1 個更小的元素 (1).
6 的右側(cè)有 1 個更小的元素 (1).
1 的右側(cè)有 0 個更小的元素.
在真實的面試中遇到過這道題？

分析

二話不說使用暴力解題（雙重遍歷）。超時。
嗯，要對代碼進(jìn)行優(yōu)化
這道題從后往前遍歷會比較清楚明了。優(yōu)化點主要在sorted這個數(shù)列。這個sorted實現(xiàn)了對遍歷到當(dāng)前i之后的數(shù)據(jù)進(jìn)行排序插入、然后就可以使用二分法進(jìn)行獲取當(dāng)前大于或者等于nums[i]的第一個位置。這個位置就是當(dāng)前值的逆序數(shù)

代碼

 class Solution {
        public List<Integer> countSmaller(int[] nums) {
            Integer[] res = new Integer[nums.length];
            //sort其實是關(guān)鍵。sort的目的是 對i后面的元素進(jìn)行從小到大的排序。
            // 每次插入新的數(shù)值，前面有幾個數(shù)就是這個數(shù)值現(xiàn)在的逆序數(shù)
            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;
                //實現(xiàn)對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;
        }
    }

結(jié)果

image.png