CPP solution based on the idea of merge_sort


  • 2
    O
    class Solution {
        vector<pair<int, int> > x;
        vector<int> ans;
    public:
        vector<int> countSmaller(vector<int>& nums) {
            for (int i = 0; i < nums.size(); i++) x.push_back(make_pair(nums[i], i));
            ans = vector<int>(x.size(), 0);
            merge_sort(0, x.size() - 1);
            return ans;
        }
        
        void merge_sort(int start, int end) {
            if (end <= start) return;
            int mid = start + (end - start) / 2;
            merge_sort(start, mid);
            merge_sort(mid + 1, end);
            merge(start, mid, mid + 1, end);
        }
        
        void merge(int start1, int end1, int start2, int end2) {
            vector<pair<int, int> > tmp;
            int p = start1, q = start2;
            while (p <= end1 && q <= end2) {
                if (x[p].first <= x[q].first) {
                    ans[x[p].second] += q - start2;
                    tmp.push_back(x[p++]);
                } else {
                    tmp.push_back(x[q++]);
                }
            }
            while (p <= end1) {
                ans[x[p].second] += q - start2;
                tmp.push_back(x[p++]);
            }
            while (q <= end2) tmp.push_back(x[q++]);
            for (int i = start1; i<= end2; i++) x[i] = tmp[i - start1];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.