手机触屏网站开发,软件外包产业是什么意思,网站开发工程师工作描述,广西网站设计公司排行榜#x1f600;前言 在算法和数据结构领域#xff0c;逆序对是一个经典问题。它在数组中两个数字之间定义#xff0c;若前面的数字大于后面的数字#xff0c;则这两个数字组成一个逆序对。我们要做的就是#xff0c;给定一个数组#xff0c;找出数组中所有的逆… 前言 在算法和数据结构领域逆序对是一个经典问题。它在数组中两个数字之间定义若前面的数字大于后面的数字则这两个数字组成一个逆序对。我们要做的就是给定一个数组找出数组中所有的逆序对并计算其总数。 个人主页尘觉主页 文章目录 数组中的逆序对问题描述示例 解题思路归并排序思想具体步骤 代码实现代码讲解时间复杂度分析 总结 数组中的逆序对
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 ) O(n^2) O(n2)这在数组规模较大时效率较低。为了解决这个问题我们可以借助归并排序算法通过将问题分解为更小的子问题来提高效率。
归并排序思想
归并排序是一种分治算法。它将一个大的问题分解为两个小的子问题递归地解决子问题最后将子问题的解合并成原问题的解。在计算逆序对时我们可以通过在归并的过程中统计逆序对的数量从而实现线性对数级别的时间复杂度 O ( n log n ) O(n \log n) O(nlogn)。
具体步骤
分解问题 将数组分成左右两部分分别对左右部分进行归并排序。归并 在归并的过程中若左半部分的某个数字大于右半部分的某个数字那么这个数字及左半部分后续的所有数字都比右半部分的数字大形成逆序对。我们可以在归并的过程中统计这些逆序对。
代码实现
以下是基于归并排序来解决逆序对问题的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 方法实现两个已排序子数组的合并过程同时统计逆序对的数量。若左边子数组的某个元素大于右边子数组的当前元素则说明该元素与右边子数组当前元素及其后的所有元素都形成了逆序对。
时间复杂度分析
归并排序的时间复杂度是 O ( n log n ) O(n \log n) O(nlogn)其中 n n n 是数组的长度。由于在归并的过程中我们只需额外进行 O ( n ) O(n) O(n) 的操作来统计逆序对因此整个算法的时间复杂度仍然是 O ( n log n ) O(n \log n) O(nlogn)。这比直接使用 O ( n 2 ) O(n^2) O(n2) 的双重循环要高效得多特别是在数组规模较大时。
总结
逆序对问题是一个经典的算法问题借助归并排序可以将其优化至 O ( n log n ) O(n \log n) O(nlogn) 的时间复杂度。通过在归并排序的过程中适时地统计逆序对我们可以有效地解决这个问题。
热门专栏推荐 想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集 linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
欢迎大家加入我的社区 尘觉社区 文章到这里就结束了如果有什么疑问的地方请指出诸佬们一起来评论区一起讨论 希望能和诸佬们一起努力今后我们一起观看感谢您的阅读 如果帮助到您不妨3连支持一下创造不易您们的支持是我的动力
