数组逆序对个数问题【1】

1. 问题描述

在一个数组中，如果存在两个下标i<j，使得array[i] > array[j]，那么称这是一个逆序对，求解数组中逆序对的个数。

例如：

array=[1,2,3,1]，返回2，（2,1）,（3,1）

数组长度len范围$[1,5000]$。

测评链接：https://www.nowcoder.com/questionTerminal/bb06495cc0154e90bbb18911fd581df6

2. 暴力解法

遍历数组，对于每一个当下下标i，都在i的右边寻找有几个数小于array[i]，累加到答案中

代码：

public class ReversePairCount {
    
    public static int count(int[] array) {
        int len = array.length, ans = 0;
        for(int i = 0; i < len; ++i) {
            for(int j = i + 1; j < len; ++j) {
                if(array[i] > array[j]) ++ans;
            }
        }
        return ans;
    }
}

时间复杂度$O(N^2)$，空间复杂度$O(1)$。

3. 最优解

3.1. 算法分析

在merge sort的merge过程中，假设左右两组都是从小到大有序的，如果我们发现左组中的一个数a，大于右组中的一个数b，那么可以知道右组中从开始到b的数，都是小于a的，因此我们可以在线性时间内，求得左组中的任何一个数，在右组中有几个数小于它。因此我们有如下算法：

假设左组的当前下标是i，左组的结束位置是m，右组的当前下标是j，右组的结束位置是r，设置一个变量ans记录当前merge中产生的所有逆序对的个数，只要i<=m成立，执行如下步骤：

1. 只要j<=r && array[j] < array[i] 成立，++j;
2. 收集答案，此时右组中有j-m-1个数小于array[i]，ans+=j-m-1;
3. ++i;

然后执行merge操作。

上游的排序过程累加每次merge产生的逆序对的个数。

3.2. 代码

public class ReversePairCount2 {
    
    public static int count(int[] array) {
        int len = array.length, ans = 0;
        if(len == 1) return ans;
        int l, m, r, g = 1;
        int[] h = new int[len];
        while(g < len) {
            l = 0;
            while(l < len - 1) {
                if((m = l + g - 1) >= len - 1) break;
                r = Math.min(len - 1, m + g);
                ans += merge(array, l, m, r, h);
                l = r + 1;
            }
            if(g > (len >> 1)) break;
            g <<= 1;
        }
        return ans;
    }
    
    private static int merge(int[] array, int l, int m, int r, int[] h) {
        int i = l, j = m + 1, k = 0, ans = 0;
        while(i <= m) {
            while(j <= r && array[j] < array[i]) ++j;// 只要满足条件，j一直跳下一个
            ans += j - m - 1;//此时右组一共有j-m-1个元素小于array[i]
            ++i;
        }
        i = l;
        j = m + 1;
        while(i <= m && j <= r) h[k++] = array[i] <= array[j] ? array[i++] : array[j++];
        while(i <= m) h[k++] = array[i++];
        while(j <= r) h[k++] = array[j++];
        System.arraycopy(h, 0, array, l, k);
        return ans;
    }
}

时间复杂度$O(N\log_2N)$，空间复杂度$O(N)$。

4. 测试程序

import java.util.*;

public class ReversePairCountTest {
    
    public static void main(String[] args) {
        int time = 100_0000, maxSize = 5000;
        while(time-- > 0) {
            Random r = new Random();
            int size = r.nextInt(maxSize) + 1;
            int[] array1 = new int[size], array2 = new int[size], array3 = new int[size];
            for(int i = 0; i < size; ++i) array1[i] = array2[i] = array3[i] = r.nextInt(101);
            int ans1 = ReversePairCount.count(array1), ans2 = ReversePairCount2.count(array2);
            if(ans1 != ans2) {
                System.out.println("Answer incorrect!, ans1: " + ans1 + ", ans2: " + ans2);
                System.out.println(Arrays.toString(array3));
                return;
            }
            System.out.println("Testcase: " + time + " success!");
        }
        System.out.println("Test done successfully!!");
    }
}