C++ 64ms mergeSort


  • 0
    A
    class Solution {
    public:
        vector<int> countSmaller(vector<int>& nums) {
            int n = nums.size();
            vector<int> res; res.reserve(n);
            if (n == 0) return res;
            if (n == 1) {
                res.push_back(0); 
                return res;
            }
            // build the mapper 
            vector<pair<int, int>> mapper; mapper.reserve(n);
            for (int i = 0; i < n; ++i){
                mapper.push_back(pair<int, int>(nums[i], i));
            }
            vector<int> ind(n, 0);
            mapper = mergeSortCount(mapper, 0, n-1, ind);
            return ind;
        }
        vector<pair<int, int>> mergeSortCount(vector<pair<int, int>>& nums, int left, int right, vector<int> & ind) {
            if (left == right) {
                vector<pair<int, int>> newVec(nums.begin() + left, nums.begin() + right + 1);
                return newVec;
            }
            int mid = left + (right - left) / 2; 
            vector<pair<int, int>> small = mergeSortCount(nums, left, mid, ind);
            vector<pair<int, int>> big = mergeSortCount(nums, mid+1, right, ind);
            vector<pair<int, int>> res(right - left + 1, pair<int, int>(0, 0));
            // cout << small[0].first << big[0].first;
            int i, j; 
            i = j = 0;
            int inv = 0;
            while (i < mid - left + 1 || j < right - mid){
                if (i == mid - left + 1) {
                    res[i + j] = big[j];
                    ++j;
                }
                else if (j == right - mid) {
                    ind[small[i].second] += inv;
                    res[i + j] = small[i];
                    ++i;
                }
                else if (small[i].first <= big[j].first){
                    ind[small[i].second] += inv;
                    res[i + j] = small[i];
                    ++i;
                }
                else if (small[i].first > big[j].first){
                    ++inv;
                    res[i + j] = big[j];
                    ++j;
                }
            }
            return res;
        }
    };

Log in to reply
 

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