C++ mergesort


  • 0
    J

    '''

    int merge(vector<long long> &a, int i, int j, int k)
    {
        int cnt = 0;
        int l1 = i, l2 = j;
        while (l1 < j && l2 < k)
        {
            while (l2 < k && a[l1] <= a[l2] * 2) l2++;
            cnt += k - l2;
            l1++;
        }
        
        l1 = i, l2 = j;
        vector<int> ret;
        while (l1 < j && l2 < k)
        {
            if (a[l1] > a[l2])
            {
                ret.push_back(a[l1++]);
            }else
            {
                ret.push_back(a[l2++]);
            }
        }
        
        while (l1 < j) ret.push_back(a[l1++]);
        while (l2 < k) ret.push_back(a[l2++]);
        for (int x = i; x < k; x++)
        {
            a[x] = ret[x - i];
        }
        
        return cnt;
    }
    
    int mergeSort(vector<long long> &a, int i, int j)
    {
        if (j - i <= 1) return 0;
        int mid = i + (j - i) / 2;
        
        int cnt = 0;
        cnt += mergeSort(a, i, mid);
        cnt += mergeSort(a, mid, j);
        cnt += merge(a, i, mid, j);
        return cnt;
    }
    
    int reversePairs(vector<int>& nums) {
        vector<long long> a;
        for (int x : nums) a.push_back(x);
        return mergeSort(a, 0, a.size());
    }
    

    '''


Log in to reply
 

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