C++, mergesort.


  • 0
    P

    2 level of indirection involved. If we mergesort, one way would be to use pairs<number, count>, another would be to have an array of index and simply sort the indices, using nums[map[i]] to retrieve the number in sorted order.

    Eg [5,2,3,4], mm = [0,1,2,3]
    after sort nums = [5,2,3,4], but mm = [1,2,3,0]. To get the sorted array, just do a nums[mm[i]] and thus nums[mm[0]] = 2, nums[mm[1]] = 3 and so on. We sort, but not the array, but the indexes and use them to retrieve.

    Now, we calculate inversions in merge sort and increment them for the appropriate index using yet another array called res,

    class Solution {
    public:
        vector<int> mm;
        vector<int>res;
        vector<int> countSmaller(vector<int>& nums) {
            vector<int>dup(nums);
            res.resize(nums.size(), 0);
            vector<int> count; int i = 0;
            for(int i = 0 ; i < nums.size(); ++i)
            {
                mm.push_back(i);
            }
            countSmaller(nums, 0, nums.size() - 1);
            return res;
        }
        
        vector<int>countSmaller(vector<int> &nums, int l, int r)
        {
            if(l < r){ //mergesort termination cond.
                int mid = l + (r - l)/2;
                countSmaller(nums, l, mid);
                countSmaller(nums,  mid + 1, r);
                merge(nums,l, r, mid);
            }
            return nums;
        }
        
        void merge(vector<int>&nums, int l, int r, int m)
        {
            vector<int>v1(mm.begin() + l, mm.begin() + m + 1); //copy the index array left.
            vector<int>v2(mm.begin() + m + 1, mm.begin() + r + 1); //copy the index array right.
            int a = 0; int b = 0; int c = 0; int k = 0;
            // Generic mergesort adapted from GeeksForGeeks, we merge back to the original index array "mm".
            while(a < v1.size() && b < v2.size())
            {
                if(nums[v1[a]] <= nums[v2[b]])
                {
                    res[v1[a]] += c;  //set the counter for the index that we sorted. 
                    mm[l + k] = v1[a];
                    a++;
                }
                else{
                    c++;
                    mm[l + k] = v2[b];
                    b++;
                }
                k++;
            }
            while(a < v1.size()) //copy the leftover. and for the left half incrmeent the counts.
            {
                res[v1[a]] +=c;
                mm[l + k++] = v1[a++];
            }
            while(b < v2.size())mm[l + k++] = v2[b++]; //copy leftover right if any.
            
            return;
            
            }
    };

Log in to reply
 

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