数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5
解释：第1个位置为7，后面3个数都可以组成逆序对，一共3组
     第2个位置为5，只有（5,4）组成逆序对，一共1组
     第3个位置为6，只有（6,4）组成逆序对，一共1组
     综上，数组[7,5,6,4]中逆序对总数为5

限制：

0 <= 数组长度 <= 50000

解题思路

方法一：暴力解法（超时）

按照逆序对的定义，使用两层循环，外层循环遍历整个数组，内存循环向后寻找。

// java
public class Solution{
    public int reversePairs(int[] nums){
        int len = nums.length ;
        int i, j ;
        int count = 0 ;
        for(i = 0; i < len; i++){
            for(j = i + 1; j < len; j++){
                if(nums[j] < nums[i])
                    count++ ;
            }
        }
        return count ;
    }
}

时间复杂度：，N是数组的长度

空间复杂度：，

方法二：归并排序改进

考虑数组中逆序对数量的一个性质：设数组A的逆序对的总数为，那么将数组A拆分为两个前后两个相邻的数组B和C，那么有 ，其中表示B中的每个数能和C中的元素组成的逆序对的总数，而且注意到如果对B或者C进行排序是不会影响到的值 ，同时如果B或者C有序（从小到大），那么有。

也就是说，我们可以通过不断地拆分原始数组，一直到每一个数组中都只有一个元素，那么一个元素的数组当然是有序的，然后依次归并各个长度为1的数组，并且保持归并后的数组有序。在归并的过程中，因为各个数组有序所以总有成立，因此只需要求即可。

原始数组：[7, 5, 6, 4, 3]
拆分结果：[7], [5], [6], [4], [3]
第一趟归并：[5, 7], [4, 6], [3]
由上述结论：f([7, 5]) = f([7]) + f([5]) + f*，数组[7]和数组[5]有序，那么f([7, 5]) = f* = 1，依次类推可以求出逆序对总数 
第二趟归并：[4, 5, 6, 7], [3]
同上面的推导过程，只需考虑数字5和数组[4, 6]能够组成逆序对的数量与数字7和数组[4, 6]能够组成逆序对的数量，这些统计是在归并中完成的。
......

可以很清晰地看到和是在上一步归并中计算得到的，只要保持每个片段都有序，那么这个计算过程就可以一直保持下去，这里采用的就是归并排序算法的框架，只需要将统计逆序对数量的过程加入到排序算法中。

/**
 *    归并排序算法一共可以分为三个部分
 *  (1) 归并两个有序片段
 *  (2) 原始数组完成一趟归并
 *  (3) 不断增加数组片段的长度，继续归并
 *  归并排序可以有不同的写法，但是其核心思想都是一致的：合并两个有序数组，并保持新数组有序
 */
class Solution{
    // (1) 区间左闭右开[start, middle), [middle, end)，归并有序片段
    int merge(int[] data, int[] temp, int start, int middle, int end)
    {
        int i = start, j = middle ;
        int t = start ;
        int cnt = 0 ;
        while(i < middle && j < end){
            if(data[i] <= data[j]){
                temp[t] = data[i] ;
                i++ ;
            }else{
                temp[t] = data[j] ;
                // 统计f*的值
                cnt += middle - i ;
                j++ ;
            }
            t++ ;
        }
        while(i < middle)
            temp[t++] = data[i++] ;
        while(j < end)
            temp[t++] = data[j++] ;
        return cnt ;
    }
    // 完成一趟归并，每个序列长度为h
    int mergePass(int[] data, int[] temp, int len, int h)
    {
        int cnt = 0 ;
        int i = 0 ;
        while(i + 2 * h < len){
            cnt += merge(data, temp, i, i+h, i+2*h) ;
            i += 2 * h ;
        }
        if(i + h < len){
            cnt += merge(data, temp, i, i + h, len);
        }else{
            // 如果h比序列长度len大，直接复制数组
            // 或者如果最后剩下1个序列，且长度不大于h，直接复制
            while(i < len){
                temp[i] = data[i] ;
                i++ ;
            }
        }
        return cnt ;
    }
    // (3) 增加序列长度，进行归并
    int reversePairs(int[] nums) {
        int cnt = 0 ;
        int h = 1 ;
        int len = nums.length ;
        int[] temp = new int[len] ;
        while(h < len){
            // 本趟归并后结果存放在temp数组中
            cnt += mergePass(nums, temp, len, h) ;
            h *= 2 ;
            // 本趟归并后结果存放在nums数组中
            cnt += mergePass(temp, nums, len, h) ;
            h *= 2 ;
        }
        return cnt ;
    }
}

时间复杂度：，N是数组的长度

空间复杂度：，使用了一个辅助数组

方法三：插入排序改进（超时）

对于一个有序序列A，假设数x在序列A之后，那么考虑序列A和数x构成的逆序对的数量，一个直接的想法就是找到数x在序列A中的位置index，那么在index到序列的A的结束的数都可以和x构成逆序对。

序列A：[7, 5, 6], 数x：4
数x在序列A中的插入位置为：index = 0，可以构成逆序对的数量：A.length - index

从一个有序序列开始（只有一个元素），每次插入一个元素，保持序列有序，计算逆序对数量，这就是一个插入排序算法

class Solution {
    public int reversePairs(int[] nums) {
        int cnt = 0 ;
        int key, j;
        for(int i = 1; i < nums.length; i++) {
            key = nums[i] ;
            // 同时进行插入和比较
            for(j = i-1; j >= 0 && key < nums[j]; j--)
                nums[j+1] = nums[j] ;
            nums[j+1] = key ;// 插入到位置index = j+1
            cnt += i - (j+1);
        }
        return cnt ;
    }
}

注意到比较的次数和插入的次数一样多，可以在已经排好序的序列中使用二分查找算法先查找到应该插入到的位置，然后再进行插入操作，从而减少比较次数，但是这样并不会改变算法的复杂度。

class Solution{
    int reversePairs(int[] nums) {
        int cnt = 0 ;
        for(int i = 1; i < nums.length; i++) {
            int key = nums[i] ;
            int lo = 0, ho = i - 1 ;
            while(lo <= ho) {
                int mid = lo + (ho-lo) / 2 ;
                if(key < nums[mid])
                    ho = mid - 1 ;
                else
                    lo = mid + 1 ;
            }
            for(int j = i-1; j >= lo; j--)
                nums[j+1] = nums[j] ;
            nums[lo] = key ;
            cnt += i - lo ;
        }
        return cnt ;
    }
}

备注：上述java代码会超时，但是可以执行到最后一个测试即（n = 50000)，可是将代码换成C语言，只能执行到30多个示例，但是在浏览题解的时候发现了一个不会超时的插入排序算法，他是用python3写的，主要调用和bisect模块。

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        cnt, tmp = 0, []
        # 逆序列表
        for num in nums[::-1]:
            index = bisect_left(tmp, num)#二分插入，计算已有列表(后面的先插入)比num小的数字
            # insort(tmp, num)
            tmp.insert(index, num)
            cnt += index ;
        return cnt

将bisect_left函数换成源码直接执行也能够通过，造成这种情况的原因可能是python的限制条件比较宽松，而C语言的时空条件都很苛刻。

时间复杂度：，N是数组的长度

空间复杂度：