For an array A, if i < j, and A [i] > A [j], called (A [i], A [j]) is a reverse pair.
return total of reverse pairs in A.
Example
Given A = [2, 4, 1, 3, 5] , (2, 1), (4, 1), (4, 3) are reverse pairs. return 3
分析：
如果用两个for loop,非常简单。但要降低复杂度，做法非常变态.简单来说，原理就是利用merge sort的方法，把左subarray 和右subarray 合并（假设它们都已排好序）。然后比较当前左subarray的第一个值是否比右边subarray第一个值大两倍，如果是，那么很明显左subarray所有的都比那个值大两倍。
class Solution {
public int reversePairs(int[] nums) {
return mergeSort(nums, , nums.length - );
}
public int mergeSort(int[] nums, int start, int end) {
if (start >= end) return ;
int total = ;
int mid = start + (end - start) / ;
total += mergeSort(nums, start, mid);
total += mergeSort(nums, mid + , end);
total += merge(nums, start, mid, end);
return total;
}
public int merge(int[] nums, int start, int mid, int end) {
int[] temp = new int[end - start + ];
int p1 = start, p2 = mid + ;
int index = ,count = ;
while (p1 <= mid && p2 <= end) {
if ((long) nums[p1] > * ((long) nums[p2])) {
count += mid - p1 + ;
p2++;
} else {
p1++;
}
}
p1 = start;
p2 = mid + ;
while (p1 <= mid && p2 <= end) {
if (nums[p1] < nums[p2]) {
temp[index++] = nums[p1++];
} else {
temp[index++] = nums[p2++];
}
}
while(p1 <= mid) {
temp[index++] = nums[p1++];
}
while(p2 <= end) {
temp[index++] = nums[p2++];
}
System.arraycopy(temp, , nums, start, end - start + );
return count;
}
}