Share my C++ MergeSort solution


  • 0

    In this problem we only need to count the number of nums[j] < nums[i] while j > i; So we can doing this while doing MergeSort.

    Assume after MergeSort, now we have the left part and the right part which are all in order. And we can know that all nums in right part is definitely on the right side of those left part nums, then for each num in left part we can count the nums smaller in the right part.

    Because we are doing this after MergeSort left part and right part, which means for each num in left part we have completely get the res in the left part domain, so do within the right part. In this way, for each num in left part, we have count the possible ans in left part, then we need to count those nums in right part. As to num in right part, we need to go through and count in its right part.

    Because the right part is in order, so we just need to go through one time!
    Codes below using two vector<int> to store the copy of nums and update indices;


    Final Codes

    class Solution
    {
        public:
            vector<int> countSmaller(vector<int> &nums)
            {
                int len = nums.size();
                vector<int> res(len, 0);
                vector<int> index;
                for(int i = 0; i < len; ++i)
                    index.push_back(i);
                vector<int> numUpdate = nums;
                vector<int> indexUpdate = index;
                solve(res, nums, index, 0, len, numUpdate, indexUpdate);
                return res;
            }
            void solve(vector<int> &res, vector<int> &nums, vector<int> &index, int start, int end, vector<int> &numUpdate, vector<int> &indexUpdate)
            {
                if(end - start <= 1)
                    return;
                int mid = (start + end) / 2;
                solve(res, nums, index, mid, end, numUpdate, indexUpdate);
                solve(res, nums, index, start, mid, numUpdate, indexUpdate);
                int r = mid;
                int t = mid;
                int s = start;
                for(int l = start; l < mid; ++l)
                {
                    while(nums[l] > nums[r] && r < end)
                        r++;
                    while(t < end && nums[t] <= nums[l])
                    {
                        numUpdate[s] = nums[t];
                        indexUpdate[s++] = index[t++];
                    }
                    numUpdate[s] = nums[l];
                    indexUpdate[s++] = index[l];
                    res[index[l]] += r - mid;
                }
                for(int i = start; i < end; ++i)
                {
                    nums[i] = numUpdate[i];
                    index[i] = indexUpdate[i];
                }
            }
    };
    

    Older Version Codes
    And the older version codes below, using a vector<pair<int, int>> to store the values and index, but using sort is not so efficient.

    bool cmp(const pair<int, int> a, const pair<int, int> b)
    {
        return a.first < b.first; 
    }
    
    class Solution
    {
        public:
            vector<int> countSmaller(vector<int> &nums)
            {
                int len = nums.size();
                vector<int> res(len, 0);
                vector<pair<int, int>> temp;
                for(int i = 0; i < len; ++i)
                    temp.push_back(make_pair(nums[i], i));
                solve(res, temp, 0, len);
                return res;
            }
            void solve(vector<int> &res, vector<pair<int, int>> &temp, int start, int end)
            {
                if(end - start <= 1)
                    return;
                int mid = (start + end) / 2;
                solve(res, temp, mid, end);
                solve(res, temp, start, mid);
                int r = mid;
                for(int l = start; l < mid; ++l)
                {
                    while(temp[l].first > temp[r].first && r < end)
                        r++;
                    res[temp[l].second] += r - mid;
                }
                sort(temp.begin() + start, temp.begin() + end, cmp);
            }
    };
    

Log in to reply
 

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