Leetcode【分治 归并排序】| 面试题51. 数组中的逆序对

题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
　输入: [7,5,6,4]
　输出: 5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof

解题

暴力解法

很容易想到依次枚举所有的前后数对进行大小比较，计算出逆序对的个数。但结果会超时。

class Solution {
    public int reversePairs(int[] nums) {
        int res = 0;
        int n = nums.length;
        if(n<2) return 0;
        for(int i = 0; i < n-1;i++){
            for(int j = i+1; j < n; j++){
                if(nums[i]>nums[j]) res++;
            }
        }
        return res;
    }
}

分治思想 归并排序

思路

分治思想：将一个问题分解为若干个子问题（一般为对半分，再对半分，递归，一直分到最小的子问题，比如数组排序最后最小的子问题就是只有两个元素），分别解决子问题，然后再将子问题合并解决合并的情况。

归并排序的分治步骤：

1. 分解：将数组nums分为左半部分l和右半部分r
2. 解决：分别归并排序左半部分l(递归重复步骤123)和归并排序右半部分r(递归重复步骤123)
3. 合并：将已排序好的左半部分l和右半部分r合并为nums排序。

在这道题中，因为排序也要比较前后元素大小，将逆序对的那些交换位置变成顺序的，因此这道题只需在归并排序的过程中同时计数逆序对即可，归并排序时递归返回的是排序后的数组，而这道题中递归返回的是计算出的逆序对的个数。故逆序对个数 = 左半部分逆序对数+右半部分逆序对数+横跨左右的逆序对数。
分治思想中，子问题的解决就一直递归直到最小的子问题即可，关键就在于合并的情况怎么解决。

左右部分合并排序其实就是：依次将当前左边最小的和右边最小的挑出来比较，选择更小的即为当前左右合并的整体最小的。min(nums) = min(min(left)，min(right))。 将当前整体最小的选出来加入排序队列再依据上述策略选择剩下元素中最小的，一直到比较完所有的元素。由于左右部分都是已经排序过的，那么左/右部分当前最小值都是当前最左边的值，所以依次从左到右挨个比较就可以了。

举个例子，因为合并的时候左半边和右半边已经都排过序了，所以我们假定当前左半部分是L= {8，12，16，22，99}，当前右半部分是R={9，26，55，64，91}。

1. 将左右两部分简单的合并起来存入临时数组temp[]就是：（分别设置左指针i和右指针j初始在两部分的最左边第一个元素）
   
   将nums[]清空储存合并后的排序结果：
   

2. 因为左/右半部分都是已经从小到大递归排序后的结果，所以合并的时候只用从左到右分别两边的最小依次比较选出更小的填入nums[]数组即可。比如上图初始化状态，当前(temp[i] = 8) < (temp[j] = 9)，说明左边最小的比右边最小的还要小，那么合并起来整体最小的就是左边最小的temp[i]，选择左边最小的填入nums[]，并将左指针右移选择剩下元素中最小的。
   

3. 再依上述策略进行剩下元素的比较，当前temp[i] > temp[j]，temp[j]为当前最小，将其填入排序数组nums[]，右指针右移选择剩下最小的：
   

4. 继续依上述策略进行剩下元素的比较，当前temp[i] < temp[j]，temp[i]为当前最小，将其填入排序数组nums[]，i++选择剩下最小的：
   

5. 继续依上述策略进行剩下元素的比较，当前temp[i] < temp[j]，temp[i]为当前最小，将其填入排序数组nums[]，i++选择剩下最小的：
   

6. 继续依上述策略进行剩下元素的比较，当前temp[i] < temp[j]，temp[i]为当前最小，将其填入排序数组nums[]，i++选择剩下最小的：
   

7. 继续依上述策略进行剩下元素的比较，当前temp[i] > temp[j]，temp[j]为当前最小，将其填入排序数组nums[]，j++选择剩下最小的：
   

8. 继续依上述策略进行剩下元素的比较，当前temp[i] > temp[j]，temp[j]为当前最小，将其填入排序数组nums[]，j++选择剩下最小的：
   

9. 继续依上述策略进行剩下元素的比较，当前temp[i] > temp[j]，temp[j]为当前最小，将其填入排序数组nums[]，j++选择剩下最小的：
   

10. 继续依上述策略进行剩下元素的比较，当前temp[i] > temp[j]，temp[j]为当前最小，将其填入排序数组nums[]，此时j已经到最右了，表示右半部分已经遍历完了，说明左半部分剩余的还未填入数组的元素都比右半部分最右/大的元素大了，依次填入nums[]中即可，故nums[i]填入数组，全部元素比较完，结束排序。
    

在上述解决归并排序的合并排序的情况中，怎么加入逆序对的计算呢？唯一出现逆序对的情况的时候就是，左指针指向数比右指针指向数大的时候，即nums[i] > nums[j]时，如上述例子中的第三步，(nums[i] = 12) > (nums[j] = 9)，因为左半部分的下标显然比右半部分的都小，所以这是(12,9)就是你虚度，而在左半部分在12右边的所有元素都比12大，与9结合都是逆序对：(16,9),(22,9),(99,9)，所以此时逆序对计数count+=(mid-i+1)。

时间复杂度：O(nlogn)
空间复杂度：O(n),因为需要一个临时数组存储原始数组供排序比较

java实现

class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        if(n < 2) return 0;
        int[] temp=new int[n];
        return recursive(nums,0,n-1,temp);//递归返回逆序对数，从整个数组开始分治
    }
    public int recursive(int[] nums,int left,int right,int[] temp){
        if(left>=right) return 0;
        int mid=(right+left)/2;
        int l=recursive(nums,left,mid,temp);//记录左半部分的逆序对数
        int r=recursive(nums,mid+1,right,temp);//记录右半部分的逆序对数
        if(nums[mid] <= nums[mid+1]) return l+r;
        return (l+r+merge(nums,left,mid,right,temp));//左+右+合并(横跨左右)      
    }
    //合并的情况
    public int merge(int[]nums,int left,int mid,int right,int[] temp){
    	for(int i=left; i<=right;i++){
    		temp[i] = nums[i];
    	}
        int count=0;
        int i = left;//初始左指针在左半部分的第一个元素
        int j = mid+1;//初始右指针在右半部分的第一个元素
        for(int k = left; k <= right; k++){//k遍历当前左右数组的合并数组的第一个元素到最后一个元素，一个个进行元素的比较选择，因为左右部分都是已经从小到大排序的，所以分别从两边的最小选出进行比较就能选出合并中当前最小的了
			if(i == mid+1){//左指针已遍历完左半部分，说明当前右指针还未遍历完的都是比左指针最后一个最大值大的，直接依次填入数组即可。
				nums[k] = temp[j];
				j++;
			}else if(j == right+1){//右指针遍历完右指针，说明当前左指针还未遍历完的都是比右指针最后一个最大值大的，直接依次填入数组即可。
				nums[k] = temp[i];
				i++;
			}else if(temp[i] <= temp[j]){//左指针所指数比右小，选择左指针所指的数填入排序后的数组，左指针后移
				nums[k] = temp[i];
				i++;
			}else if(temp[i] > temp[j]){//左指针所指数比右大，因为左指针指的是左半部分的，下标肯定都比右指针指的小，所以此时就是逆序对，选择更小的右指针所指数填入数组，右指针后移
				nums[k] = temp[j];
				j++;
				count += (mid-i+1);//表示在这个左指针往右的所有左半部分数组和该右指针都能组成逆序对
            }
		}
        
        return count;
    }
}

参考：力扣官方题解