C++ solution , NOT Merge Sort based


  • 0
    C
    class Solution {
    public:
        int reversePairs(vector<int>& nums) {
            int res = 0;
            vector<long long> n;
            for (int i = nums.size()-1; i >= 0; i--)
            {
                auto it = upper_bound(n.begin(), n.end(), nums[i]);
                res += it - n.begin();
                it = upper_bound(n.begin(), n.end(), nums[i] * 2ll);
                n.insert(it, 2ll * nums[i] + 1);
            }
            return res;
        }
    };
    
    

Log in to reply
 

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