Reverse Pairs

给一个数组, 定义revrese pair是(i,j) nums[i] > 2*nums[j]. 问有几对儿, 这个和普通的reverse pairs没啥区别. 只是多个倍数. 经典算法之一, 这个应该用divide and conquer来做. 注意每次divide完了都sort一下.

public class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length-1);
    }
    private int mergeSort(int[] nums, int s, int e){
        if(s>=e) {
            return 0;
        }
        int mid = s + (e-s)/2; 
        int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e); //divide
        for(int i = s, j = mid+1; i<=mid; i++){ // i 
            while(j<=e && nums[i]/2.0 > nums[j]) { // nums[j]*2 is too big
                j++;
            }
            cnt += j-(mid+1); //conquer
        }
        Arrays.sort(nums, s, e+1); 
        return cnt; 
    }
}