[LeetCode] 315. Count of Smaller Numbers After Self 計算后面較小數字的個數

You are given an integer array nums and you have to return a new counts array. The countsarray has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

這道題給定了一個數組，讓我們計算每個數字右邊所有小于這個數字的個數，目測不能用 brute force，OJ 肯定不答應，那么為了提高運算效率，首先可以使用用二分搜索法，思路是將給定數組從最后一個開始，用二分法插入到一個新的數組，這樣新數組就是有序的，那么此時該數字在新數組中的坐標就是原數組中其右邊所有較小數字的個數，參見代碼如下：

解法一:

// Binary Search
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> t, res(nums.size());
        for (int i = nums.size() - 1; i >= 0; --i) {
            int left = 0, right = t.size();
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (t[mid] >= nums[i]) right = mid;
                else left = mid + 1;
            }
            res[i] = right;
            t.insert(t.begin() + right, nums[i]);
        }
        return res;
    }
};

上面使用二分搜索法是一種插入排序的做法，我們還可以用 C++ 中的 STL 的一些自帶的函數，比如求距離 distance，或是求第一個不小于當前數字的函數 lower_bound()，這里利用這兩個函數代替了上一種方法中的二分搜索的部分，兩種方法的核心思想都是相同的，構造有序數組，找出新加進來的數組在有序數組中對應的位置存入結果中即可，參見代碼如下：

解法二：

// Insert Sort
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> t, res(nums.size());
        for (int i = nums.size() - 1; i >= 0; --i) {
            int d = distance(t.begin(), lower_bound(t.begin(), t.end(), nums[i]));
            res[i] = d;
            t.insert(t.begin() + d, nums[i]);
        }
        return res;
    }
};

再來看一種利用二分搜索樹來解的方法，構造一棵二分搜索樹，稍有不同的地方是需要加一個變量 smaller 來記錄比當前結點值小的所有結點的個數，每插入一個結點，會判斷其和根結點的大小，如果新的結點值小于根結點值，則其會插入到左子樹中，此時要增加根結點的 smaller，并繼續遞歸調用左子結點的 insert。如果結點值大于根結點值，則需要遞歸調用右子結點的 insert 并加上根結點的 smaller，并加1，參見代碼如下：

解法三：

// Binary Search Tree
class Solution {
public:
    struct Node {
        int val, smaller;
        Node *left, *right;
        Node(int v, int s) : val(v), smaller(s), left(NULL), right(NULL) {}
    };
    int insert(Node*& root, int val) {
        if (!root) return (root = new Node(val, 0)), 0;
        if (root->val > val) return root->smaller++, insert(root->left, val);
        return insert(root->right, val) + root->smaller + (root->val < val ? 1 : 0);
    }
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size());
        Node *root = NULL;
        for (int i = nums.size() - 1; i >= 0; --i) {
            res[i] = insert(root, nums[i]);
        }
        return res;
    }
};