Reverse Pairs (Leetcode 493, Lin

本周竞赛题，这道题与Lintcode上面的reverse pair大同小异。这类题求个数，思路就是用merge sort. 由于两边的Array部分都是已经sort好的了，当左边的left index满足条件时，左边left往后的所有element都会满足条件，此时的个数为mid - left + 1,

下面是mergeSort的 in place做法. 非常行
https://discuss.leetcode.com/topic/78953/c-solution-using-merge-sort

class Solution {
public:

    void merge(vector<int>& nums, int start, int mid, int end){
        int left = start, right = mid + 1;
        while(left <= mid && right <= end){
            if((long)nums[left] <= (long)2 * nums[right]){
                left++;
            }else{
                cnt += mid - left + 1;
                right++;
            }
        }
        sort(nums.begin() + start, nums.begin() + end + 1);
    }

    void merge_sort(vector<int>& nums, int start, int end){
        if(start >= end) return;
        int mid = start + (end-start)/2;
        merge_sort(nums, start, mid);
        merge_sort(nums, mid+1, end);
        merge(nums, start, mid, end);
    }

    int reversePairs(vector<int>& nums) {
        if(nums.empty()) return 0;
        merge_sort(nums, 0, nums.size()-1);
        return cnt;
    }
private:
    int cnt = 0;
};

Lintcode 532:

只是去除了两倍关系

class Solution {
public:
    /**
     * @param A an array
     * @return total of reverse pairs
     */
    
    void merge(vector<int>& A, int start, int mid, int end){
        int left = start, right = mid+1;
        while(left <= mid && right <= end){
            if(A[left] <= A[right]){
                left++;
            }else{
                cnt += mid - left + 1;
                right++;
            }
        }
        sort(A.begin() + start, A.begin() + end + 1);
    }
    
    void mergeSort(vector<int>& A, int start, int end){
        if(start >= end) return;
        int mid = start + (end-start)/2;
        mergeSort(A, start, mid);
        mergeSort(A, mid+1, end);
        merge(A, start, mid, end);
    } 
     
    long long reversePairs(vector<int>& A) {
        // Write your code here
        if(A.empty()) return 0;
        mergeSort(A, 0, A.size()-1);
        return cnt;
        
    }
private:
long long cnt = 0;
};

另外一种方法是通过insertion sort + binary search, 这里列出Leetcode 315题的解法. 我们建立一个空的数组，把原数组从后往前loop (注意顺序). 由于新数组保持有序的，所以插入时元素所在位置，就等价于该元素所满足的pair个数.

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        if(nums.empty()) return vector<int>();
        int size = nums.size();
        vector<int> ret(nums.size(), 0);
        vector<int> v;
        for(int i=nums.size()-1; i>=0; i--){
            int left = 0, right = v.size();
            while(left < right){
                int mid = left + (right-left)/2;
                if(v[mid] < nums[i]){
                    left = mid + 1;
                }else{
                    right = mid;
                }
            }
            ret[i] = right;
            v.insert(v.begin()+right, nums[i]);
        }
        return ret;
    }
};

同时，这道题自己建立BST解也是相当方便.
https://discuss.leetcode.com/topic/78943/clean-java-solution-using-enhanced-binary-search-tree/2

class TreeNode{
    int val;
    int count;
    TreeNode left, right;
    TreeNode(int v){
        val = v;
        count = 1;
    }
}

public class Solution {
    
    private int query(TreeNode root, double value){
        if(root == null) return 0;
        if(root.val < value){
            return root.count + query(root.right, value);
        }else{
            return query(root.left, value);
        }
    }
    
    private TreeNode insert(TreeNode root, int value){
        
        if(root == null) return new TreeNode(value);
        if(root.val == value) root.count++;
        else if(root.val > value){
            root.count++;
            root.left = insert(root.left, value);
        }else{
            root.right = insert(root.right, value);
        }
        return root;
    }
    
    public int reversePairs(int[] nums) {
        if(nums == null || nums.length < 2) return 0;
        TreeNode root = new TreeNode(nums[nums.length-1]);
        int ret = 0;
        for(int i=nums.length-2; i>=0; i--){
            ret += query(root, nums[i] / 2.0);
            insert(root, nums[i]);
        }
        return ret;
    }
}