C++ Clean & Short, MergeSort Based


  • 0
    F
    class Solution {
        int merge_sort(vector<int> & nums, int l, int h)
        {
            if (l >= h - 1)
                return 0;
            int mid = (l + h) / 2;
            int count = merge_sort(nums, l, mid) + merge_sort(nums, mid, h);
            vector<int> temp;
            int i = l, j = mid;
            while (i < mid && j < h) //this pass only counts
            {
                if (nums[i] <= (long long)nums[j] * 2)
                    i ++;
                else
                {
                    count += mid - i;
                    j ++;
                }
            }
            i = l, j = mid;
            while (i < mid && j < h) //this pass merges
                if (nums[i] <= nums[j])
                    temp.push_back(nums[i ++]);
                else
                    temp.push_back(nums[j ++]);
            while (i < mid)
                temp.push_back(nums[i ++]);
            while (j < h)
                temp.push_back(nums[j ++]);
            for (int i = l; i < h; ++ i)
                nums[i] = temp[i - l];
            return count;
        }
    public:
        int reversePairs(vector<int>& nums) {
            return merge_sort(nums, 0, nums.size());
        }
    };
    

Log in to reply
 

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