算法的学习笔记—数组中的逆序对(牛客JZ51)

在这里插入图片描述

????前言
在算法和数据结构领域，"逆序对"是一个经典问题。它在数组中两个数字之间定义，若前面的数字大于后面的数字，则这两个数字组成一个逆序对。我们要做的就是，给定一个数组，找出数组中所有的逆序对并计算其总数。

????个人主页：尘觉主页

文章目录

????数组中的逆序对
- ????问题描述
- - 示例
- ????解题思路
- - 归并排序思想
  - 具体步骤
- ????代码实现
- - 代码讲解
  - 时间复杂度分析
- ????总结

????数组中的逆序对

NowCoder

????问题描述

给定一个数组，数组中的两个数字如果满足以下条件，则它们组成一个逆序对：

假设数组为 nums[i] 和 nums[j]，若 i < j 并且 nums[i] > nums[j]，则 (nums[i], nums[j]) 是一个逆序对。

目标是计算数组中这样的逆序对的数量。

示例

假设给定的数组为 [7, 5, 6, 4]。通过观察可以得到以下逆序对：

(7, 5)
(7, 6)
(7, 4)
(5, 4)
(6, 4)

总共有 5 对逆序对，因此最终结果为 5。

????解题思路

直接使用双重循环暴力枚举每一对元素来检查是否为逆序对的复杂度为 $O(n^2)$ ，这在数组规模较大时效率较低。为了解决这个问题，我们可以借助归并排序算法，通过将问题分解为更小的子问题来提高效率。

归并排序思想

归并排序是一种分治算法。它将一个大的问题分解为两个小的子问题，递归地解决子问题，最后将子问题的解合并成原问题的解。在计算逆序对时，我们可以通过在归并的过程中统计逆序对的数量，从而实现线性对数级别的时间复杂度 $\log n)$ 。

具体步骤

分解问题： 将数组分成左右两部分，分别对左右部分进行归并排序。
归并： 在归并的过程中，若左半部分的某个数字大于右半部分的某个数字，那么这个数字及左半部分后续的所有数字都比右半部分的数字大，形成逆序对。我们可以在归并的过程中统计这些逆序对。

????代码实现

以下是基于归并排序来解决逆序对问题的Java代码实现：

private long cnt = 0;  // 用于计数逆序对的数量
private int[] tmp;  // 辅助数组，避免在递归过程中多次创建新数组

public int InversePairs(int[] nums) {
    tmp = new int[nums.length];
    mergeSort(nums, 0, nums.length - 1);
    return (int) (cnt % 1000000007);  // 结果对1000000007取模，防止结果过大
}

private void mergeSort(int[] nums, int l, int h) {
    if (h - l < 1)  // 当子数组的长度小于等于1时，不需要进行排序
        return;
    int m = l + (h - l) / 2;  // 计算中间位置
    mergeSort(nums, l, m);  // 递归排序左半部分
    mergeSort(nums, m + 1, h);  // 递归排序右半部分
    merge(nums, l, m, h);  // 合并排序后的两个子数组
}

private void merge(int[] nums, int l, int m, int h) {
    int i = l, j = m + 1, k = l;  // 初始化左右指针和辅助数组的指针
    while (i <= m || j <= h) {  // 当左、右两部分数组未完全处理完时
        if (i > m) {
            tmp[k] = nums[j++];  // 左边处理完了，直接将右边的元素加入辅助数组
        } else if (j > h) {
            tmp[k] = nums[i++];  // 右边处理完了，直接将左边的元素加入辅助数组
        } else if (nums[i] <= nums[j]) {
            tmp[k] = nums[i++];  // 左边元素小于等于右边元素，加入辅助数组
        } else {
            tmp[k] = nums[j++];  // 右边元素小于左边元素，加入辅助数组
            cnt += m - i + 1;  // 统计逆序对，左边的剩余元素都比当前右边元素大
        }
        k++;
    }
    // 将辅助数组的结果复制回原数组
    for (k = l; k <= h; k++)
        nums[k] = tmp[k];
}

代码讲解

cnt：用于计数逆序对的总数量。
tmp：辅助数组，用于在归并时暂存排序后的子数组。
InversePairs 方法：对输入数组调用归并排序，并返回逆序对数量。为了避免结果过大，返回时对 1000000007 取模。
mergeSort 方法：实现归并排序的递归逻辑，将数组分为两部分，分别进行排序，并在排序过程中调用 merge 方法。
merge 方法：实现两个已排序子数组的合并过程，同时统计逆序对的数量。若左边子数组的某个元素大于右边子数组的当前元素，则说明该元素与右边子数组当前元素及其后的所有元素都形成了逆序对。

时间复杂度分析

归并排序的时间复杂度是 $\log n)$ ，其中 $n$ 是数组的长度。由于在归并的过程中我们只需额外进行 $O (n)$ 的操作来统计逆序对，因此整个算法的时间复杂度仍然是 $\log n)$ 。这比直接使用 $O(n^2)$ 的双重循环要高效得多，特别是在数组规模较大时。

????总结

逆序对问题是一个经典的算法问题，借助归并排序可以将其优化至 $\log n)$ 的时间复杂度。通过在归并排序的过程中适时地统计逆序对，我们可以有效地解决这个问题。

????热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

????欢迎大家加入我的社区尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论????
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读????
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力????

秒客网