[LeetCode] Count of Smaller Numbers After Self

https://leetcode.com/problems/count-of-smaller-numbers-after-self/#/description

解法1：暴力

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        if (nums.empty()) return vector<int>();
        
        int n = nums.size();
        vector<int> count(n, 0);
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[j] < nums[i]) count[i]++;
            }
        }
        
        return count;
    }
};

注：暴力会超时。

解法2：归并排序

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        if (nums.empty()) return vector<int>();
        
        int n = nums.size();
        vector<int> count(n, 0);
        vector<pair<int, int> > nodes;  // pair: (val, idx)
        for (int i = 0; i < n; ++i) {
            nodes.push_back(make_pair(nums[i], i));
        }
        solve(count, nodes, 0, n-1);
        
        return count;
    }
private:
    void solve(vector<int>& count, vector<pair<int, int> >& nodes, int start, int end) {
        if (start >= end) return;
        
        int mid = start + (end - start) / 2;
        solve(count, nodes, start, mid);
        solve(count, nodes, mid+1, end);
        merge(count, nodes, start, mid, end);
    }
    
    void merge(vector<int>& count, vector<pair<int, int> >& nodes, int start, int mid, int end) {
        vector<pair<int, int> > helper(end - start + 1);
        int p = start, q = mid + 1, r = 0;
        while (p <= mid && q <= end) {
            if (nodes[p].first > nodes[q].first) {
                count[ nodes[p].second ] += (end - q + 1);
                helper[r++] = nodes[p++];
            } else {
                helper[r++] = nodes[q++];
            }
        }
        while (p <= mid) helper[r++] = nodes[p++];
        while (q <= end) helper[r++] = nodes[q++];
        copy(helper.begin(), helper.end(), nodes.begin() + start);
    }
};