二分查找与排序

相似解法题目多元组

• 归并排序：< BM20 数组中的逆序对，BM5 合并 k 个已排序的链表，BM12 单链表的排序 >

BM20 数组中的逆序对

描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将 P 对 1000000007 取模的结果输出。 即输出 P mod 1000000007。

题目保证输入的数组中没有的相同的数字。

思路

归并排序

在归并排序过程中会将数组换分成最小为 1 个元素的子数组，然后依次比较子数组的每个元素的大小，依次取出较小的一个合并成大的子数组。

主要流程：取中间 -> 左右划分 -> 合并

我们可以用相同的方法划分，划分之后相邻一个元素的子数组可以根据大小统计逆序对。在不断往上合并的时候，因为已经排好序了，逆序对可以向上累计。

F1：归并排序

步骤

1. 划分阶段：将待划分区间从中点划分成两部分，两部分进入递归继续划分，直到子数组长度为 1。
2. 排序阶段：
   • 使用归并排序递归地处理子序列，同时统计逆序对，因为在归并排序中，我们会依次比较相邻两组子数组各个元素的大小，并累计遇到的逆序情况。
   • 对排好序的两组，右边大于左边时，它大于了左边的所有子序列，基于这个性质，我们可以不用每次加 1 来统计，减少运算次数。
3. 合并阶段：将排好序的子序列合并，同时累加逆序对。

归并排序统计逆序对

代码

public static int mod = 1000000007;
public int inversePairs(int[] array) {
    int n = array.length;
    int[] help = new int[n];
    return mergeSort(0, n - 1, array, help);
}

// 计算逆序对的总数
public int mergeSort(int left, int right, int[] data, int[] help) {
    // 停止划分
    if (left >= right) // base case
        return 0;
    // 取中间
    int mid = left + ((right - left) >> 1);
    // 左右划分合并
    int res = mergeSort(left, mid, data, help) + mergeSort(mid + 1, right, data, help);
    // 防止溢出
    res %= mod;
    int i = left, j = mid + 1; // 左、右指针
    // 将当前划分的数组全部填充到辅助数组中
    for (int k = left; k <= right; k++) {
        help[k] = data[k];
    }
    for (int k = left; k <= right; k++) {
        if (i == mid + 1) { // 左指针到边界，后续只需右指针移动
            data[k] = help[j]; // 填充右边的值
            j++;
        } else if (j == right + 1) { // 如果右指针到边界
            data[k] = help[i]; // 填充左边的值
            i++;
        } else if (help[i] <= help[j]) { // 左指针的值 <= 右指针的值
            data[k] = help[i];
            i++;
        } else { // 左右指针都没越界，左指针的值 > 右指针的值
            data[k] = help[j]; // 填充右边的值
            j++;
            // 符合逆序对的定义
            res += mid - i + 1;
        }
    }
    return res % mod;
}

时间复杂度

\(O(nlog_2n)\)

归并排序利用分治思想，树形递归每次二分，总共能分为 \(log_2n\) 层，每层合并都需要遍历数组所有元素，即 \(O(n)\)。

空间复杂度

\(O(n)\)

辅助数组 help 长度为 n 及递归栈最大深度不会超过 n。