解題思路：

歸并排序，在歸并的過程中不斷計算逆序對的個數

count += mid -i + 1；的來源見下圖，因為兩個數組都是單調遞增的，所以如果第一個數組的前一個元素大于第二個數組的對應元素，那么第一個數組的這一元素的后面的元素都會大于第二個數組的對應元素。

例如下面的例子：因為2>0，由兩個數組都單調遞增可知，2后面的元素都大于0，此時4個逆序對使得count增加4。

class Solution {//利用歸并排序解答，在合并的時候，當左邊的大于右邊，就計算逆序數。//計算公式； mid-left+1//定義一個全局的計數器變量int count = 0;public int reversePairs(int[] nums) {mergeSort(nums, 0, nums.length-1);return count;}public void mergeSort(int[] nums,int left,int right){//當只有一個節點的時候，直接返回，退出遞歸if(left >= right){return;}int mid = (left+right)/2;//左拆分mergeSort(nums,left,mid);//右拆分mergeSort(nums,mid+1,right);//合并merge(nums,left,mid,right);}public void merge(int[] nums,int left,int mid,int right){//定義一個臨時數組int[] temp = new int[right-left+1];//定義一個指針，指向臨時數組的第一個元素int t = 0;//定義一個指針，指向第一個數組的第一個元素int i = left;//定義一個指針，指向第二個數組的第一個元素int j = mid+1;        //當兩個數組都有元素的時候，遍歷比較每個元素大小while(i <= mid && j <= right){//比較兩個數組的元素，取較小的元素加入到，臨時數組中//并將兩個指針指向下一個元素if(nums[i] <= nums[j]){temp[t++] = nums[i++];}else{//當左邊數組的大與右邊數組的元素時，就對當前元素以及后面的元素的個數進行統計，//此時這個數就是，逆序數//定義一個計數器，記下每次合并中存在的逆序數。count += mid-i+1;temp[t++] = nums[j++];}}//當左邊的數組沒有遍歷完成后，直接將剩余元素加入到臨時數組中while(i <= mid)temp[t++] = nums[i++];//當右邊的數組沒有遍歷完成后，直接將剩余元素加入到臨時數組中while(j <= right)temp[t++] =nums[j++];//將新數組中的元素，覆蓋nums舊數組中的元素。//此時數組的元素已經是有序的for(int k =0; k< temp.length;k++){nums[left+k] = temp[k];}}
}