剑指 Offer 51. 数组中的逆序对

剑指 Offer 51. 数组中的逆序对

这题和归并排序联系紧密，使用归并排序时比较前后两个区间中的数，由于这两个区间都是升序的，因此如果左区间的一个数大于右区间的一个数，那么左区间的该数以及其右边的数全都大于右区间的此数，即mid - i + 1个逆序对，因为归并特性，该右区间的数不会再碰到此逆序对中的任何一个数，证明了此方法的正确性

注：使用归并如果temp数组如果写在merge方法中，创建多次temp数组此题会超时，可以将temp数组作为一个公共数组传参。

class Solution {
    int count = 0;
    public int reversePairs(int[] nums) {
        //O(m*n)复杂度太高，使用归并排序刚好符合此题特点
        if(nums.length == 0) return 0;
        int[] temp = new int[nums.length];
        mergeSort(nums, 0, nums.length-1,temp);
        return count;
    }
    void mergeSort(int[] nums,int low,int high,int[] temp){
		if(low == high) return;
		else{
			int mid = (low + high) / 2;
			mergeSort(nums,low,mid,temp);
			mergeSort(nums,mid + 1,high,temp);
			merge(nums,low,mid,high,temp);
		}
	}
	private void merge(int[] nums, int low, int mid, int high,int[] temp) {
		
		int i = low,j = mid + 1;
		int m = mid,n = high;
		int k = 0;
		while(i <= m && j <= n){
			if(nums[i] <= nums[j]) temp[k++] = nums[i++];
			else{
                count += (mid - i + 1); //归并排序加上此行   比如2 4 6  和 1 3 5  指针指向2和1时，2比1大，说明2后面数字也一定比1大，所以对于数字1作为较小值的逆序对数量是46，归并后它们的数字不会再相会，证明这个方法的正确性
                temp[k++] = nums[j++]; 
            } 
		}
		while(i <= m){
			temp[k++] = nums[i++];
		}
		while(j <= n){
			temp[k++] = nums[j++];
		}
		for(int x = low;x <= high;x++){
			nums[x] = temp[x - low];
		}
		
	}
}