Reverse Pairs

Java

public class Solution {
    /**
     * @param A: an array
     * @return: total of reverse pairs
     */
		public long reversePairs(int[] A) {
			return mergeSort(A, 0, A.length - 1);
		}
		//mergeSort模版
		private int mergeSort(int[] nums, int left, int right) {
			if (left >= right) { //递归退出条件
				return 0;
			}
			int mid = left + (right - left) / 2;
			int res = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);
			res += merge(nums, left, right, mid); //先加左右结果，再加本层merge的结果
			return res;
		}
		//利用 mergeSort中 merge的步骤特性，来计算逆序对的数量
		private int merge(int[] nums, int left, int right, int mid) {
			int res = 0;
			int[] merged = new int[right - left + 1]; //临时数组
			int i = left, j = mid + 1, index = 0; //临时数组的指针
			while (i <= mid && j <= right) {
				if (nums[i] <= nums[j]) {
				merged[index++] = nums[i++];
				} else {
					merged[index++] = nums[j++];
					//calculus res 
					res += mid - i + 1; //这个 j 可以和左边的所有数字都成逆序对
				}
			}
			while (i <= mid) {
				merged[index++] = nums[i++];
			}
			while (j <= right) {
				merged[index++] = nums[j++];
			}
			for (i = left, index = 0; i <= right; i++, index++) {
				nums[i] = merged[index]; //排好序的数组就不会
			}
			return res;
		} 	
}