劍指 Offer 51. 數組中的逆序對

在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。輸入一個數組，求出這個數組中的逆序對的總數。

示例 1:

輸入: [7,5,6,4]
輸出: 5

限制：

0 <= 數組長度 <= 50000

解題思路

在歸并排序中，穿插逆序對的計算，歸并兩個排序數組時當出現右區間元素，大于左區間元素的時候，說明左區間內的元素和當前元素都能組成逆序對

代碼

class Solution {int cnt=0;public int reversePairs(int[] nums) {mergeSort(nums,0,nums.length-1);return cnt;}public void mergeSort(int[] nums,int l,int r){int mid=(r-l)/2+l;if(l<r){mergeSort(nums,l,mid);mergeSort(nums,mid+1,r);merge(nums,l,r);}}public void merge(int[] nums,int l,int r){int[] t=new int[r-l+1];int mid=(r-l)/2+l;int i=l,j=mid+1,idx=0;while(i<=mid&&j<=r){if(nums[i]<=nums[j])t[idx++]=nums[i++];else{cnt+=mid-i+1;t[idx++]=nums[j++];}  }while(i<=mid)t[idx++]=nums[i++];while(j<=r)t[idx++]=nums[j++];for(int k=0;k<r-l+1;k++)nums[l+k]=t[k];}
}