侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

51 数组中的逆序对

Lin2J
2021-07-21 / 0 评论 / 0 点赞 / 152 阅读 / 1,968 字 / 正在检测是否收录...

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

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

解题思路:

通过归并排序分治思想计算逆序对:

  • 分:不断将数组进行二分,将整个数组的排序问题转化为子数组的排序问题;
  • 治:当数组长度为 $1$ 时,开始向上合并,将 较短的排序数组 合并成 较长的排序数组,直到合并至原来数组时,完成排序;

合并阶段本质上是合并两个有序数组,可以在这个阶段进行逆序对的统计。下面假设合并到原来数组时,总体分为两个数组,左数组 $[0, 3]$ 和右数组 $[4, 7]$。

51-两个有序数组

统计过程:

  1. 使用指针$i$,$j$ ,初始值为 $i = 0$,$j = mid+1$。
  2. 当 $i$ 指向的元素比 $j$ 指向的元素大时,则 ${nums[i], nums[j]}$组成一个逆序对。不但如此,因为两个子数组是有序的,所以实际上 $[i, mid]$ 之间的元素都可以与 $nums[j]$ 组成逆序对。因此,对于 $nums[j]$ 来说,有 $mid - i + 1$ 个逆序对。
  3. 当 $i = 2$ 和 $j = 6$ 时,也是一样的计算方式。

将上述过程总结一下就是:

合并左右子数组时,如果 左子数组当前元素 大于 右子数组当前元素时,意味着 [左子数组当前元素至末尾元素] 与 [右子数组当前元素] 构成 若干个 [逆序对]。

两个关键点就是:① 发生在合并两个有序子数组时;② 左子数组当前元素大于右子数组当前元素。

那么其实就是在归并排序的基础上,加上一行统计逆序对的代码即可。

代码:

private int ans = 0;

public int reversePairs(int[] nums) {
    mergeSort(nums, 0, nums.length - 1);
    return ans;
}

private void mergeSort(int[] nums, int l, int r) {
    if (l >= r) {
        return;
    }
    int mid = (l + r) / 2;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);
    merge(nums, l, mid, r);
}

private void merge(int[] nums, int l, int mid, int r) {
    int[] tmp = new int[r - l + 1];
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            // 计算逆序对,相比于归并排序,只多了这一句代码
            ans += mid - i + 1;
            tmp[k++] = nums[j++];
        }
    }
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= r) {
        tmp[k++] = nums[j++];
    }
    for (k = 0; k < tmp.length; k++) {
        nums[k + l] = tmp[k];
    }
}

复杂度分析

  • 时间复杂度$O(NlogN)$:归并排序使用 $O(NlogN)$ 时间。
  • 空间复杂度$O(N)$:整个过程创建辅助数组的长度为 $N$。
0

评论区