[LeetCode] 493. Reverse Pairs

https://leetcode.com/contest/leetcode-weekly-contest-19/problems/reverse-pairs/

Solution:

The straightforward way is of O(n2) time complexity, which is not accepted by the OJ. So we need to find a quicker way. One way is to sort the processed elements. The details are that we will start from the end of the original vector, then gradually built a sorted vector as the processing goes. For each later element in the original vector, we just need to find the index of the element whose double value is smaller than the target element. Because that we start with the end of the original vector, all the elements inside the sorted vector have larger index than the target element in the original vector. Since we will do this in a sorted vector, the time complexity can be O(ln n) by using standard binary search. After we know many elements satisfy the condition, we can insert the target element into the sorted vector in the right position. So it will be O(ln n) again. The overall time complexity is (nln n). We may also need to use long long to avoid possible overflow problem. See code below. 

There's maybe even faster way to do it, will update later. Stay tuned.

Code:

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int res = 0, n = nums.size();
        if(n<2) return res;
        vector<long long> v;
        v.push_back(2*(long long)nums[n-1]);
        for(int i=n-2; i>=0; --i){
            int ind1 = findP(v, (long long)nums[i]);
            res += ind1;
            int ind2 = findP(v, 2*(long long)nums[i]);
            v.insert(v.begin()+ind2, 2*(long long)nums[i]);
        }
        return res;
    }
private:
    int findP(vector<long long> &v, long long t){
        int left = 0, right = v.size();
        while(left<right){
            int mid = left + (right-left)/2;
            if(v[mid] < t) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};