C++ solution with Merge Sort


  • 0
    S
    class Solution {
    public:
        int ans;
        vector<int> nut;
        
        void merge(vector<int>& nums, int st1, int ed1, int st2, int ed2) {
        	int i = st1, j = st2, k = 0;
        	while (i <= ed1 && j <= ed2) {
        	    if (nums[i] / 2 > nums[j]) {
        	        ans += (ed2 - j + 1);
        	        ++i;
        	    } else if (nums[i] / 2 == nums[j]) {
        	        if (nums[i] >= 0 && (nums[i] & 1)) {
        	            ans += (ed2 - j + 1);
        	            ++i;
        	        } else {
        	            ++j;
        	        }
        	    } else {
        	        ++j;
        	    }
        	}
            
            // standard merge
            i = st1, j = st2, k = 0;
            while (i <= ed1 && j <= ed2) {
                if (nums[i] > nums[j]) {
                    nut[k++] = nums[i++];
                } else {
                    nut[k++] = nums[j++];
                }
            }
        	while (i <= ed1) nut[k++] = nums[i++];
        	while (j <= ed2) nut[k++] = nums[j++];
        	for (int i = 0; i < k; ++i) {
        		nums[st1 + i] = nut[i];
        	}
        }
        
        void merge_sort(vector<int>& nums, int left, int right) {
        	if (left >= right) return;
        	int m = (left + right) / 2;
        	merge_sort(nums, left, m);
        	merge_sort(nums, m + 1, right);
        	merge(nums, left, m, m + 1, right);
        }
        
        int reversePairs(vector<int>& nums) {
        	int n = nums.size();
        	nut = vector<int>(n, 0);
        	ans = 0;
        	merge_sort(nums, 0, n - 1);
        	return ans;
        }
    };
    

Log in to reply
 

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