\color{green}{<–画图不易,点下这里赞一下吧}
逆序对的定义:在一个数字数组中,如果存在索引 i 和 j(其中 i < j),使得 arr[i] > arr[j],则称其为一个逆序对。
暴力解法:
- 最简单的计算逆序对的方法是通过两层嵌套循环遍历数组,比较每一对元素,并在找到逆序对时递增计数器。然而,这种方法的时间复杂度为 O(n^2),对于大型数组可能效率较低。
基于归并排序的解法
一种高效的计算逆序对的方法是使用修改后的归并排序算法。基本思想是将数组分割为较小的子数组,递归地对它们进行排序,然后在合并过程中计算逆序对。
-
归并排序步骤:将数组递归地分割为两半,直到每个子数组只有一个元素。然后,将子数组按照排序顺序合并回来,同时在合并过程中计算逆序对。
-
合并过程中计算逆序对:在合并两个已排序的子数组时,如果发现逆序对(即 arr[i] > arr[j]),则将逆序对的数量递增为第一个子数组中剩余的元素数量(即 (mid - i + 1),其中 mid 是合并的子数组的中间索引)。
-
这是因为在合并过程中,如果左边的子数组元素 arr[i] 大于右边的子数组元素 arr[j],则 arr[i] 大于右边子数组中的所有元素,形成逆序对。
示例
假设一个数组 arr = [4, 3, 2, 1]。
使用基于归并排序的方法,我们可以如下计算逆序对的数量:
-
初始数组:
[4, 3, 2, 1]
-
归并排序步骤1:
[4, 3, 2, 1] -> [4, 3], [2, 1]
-
归并排序步骤2:
[4, 3], [2, 1] -> [4], [3], [2], [1]
-
归并排序步骤3:合并
[4], [3]
,得到[3, 4]
-
合并过程中计算逆序对:
[4]
与[3]
合并,总逆序对数量 = 1(因为 4 > 3 且 且 4 后面没有其他元素) -
归并排序步骤4:合并
[2]
,[1]
, 得到[1, 2]
-
合并过程中计算逆序对:
[2]
与[1]
合并,总逆序对数量 = 1(因为 2 > 1 且 且 2 后面没有其他元素) -
归并排序步骤5:
[3, 4], [1, 2] -> [1, 2, 3, 4]
-
合并过程中计算逆序对:
[3, 4]
与[1, 2]
合并,总逆序对数量 = 4(最开始 3 和 1 比较,因为3 > 1
, 所以逆序对为mid - l + 1 = 1 - 0 + 1 = 2
个。 接下来3 与 2 比较:因为3 > 2
, 所以逆序对为mid - l + 1 = 1 - 0 + 1 = 2
个。) -
最终逆序对数量:1 + 1 + 2 + 2 = 6
- 时间复杂度:该方法的时间复杂度为 O(n log n)。
- 归并排序合并过程中计算逆序对数量
- 若 a[i] > a[j],则a[i] 和它后面的元素都大于 a[j],a[i] 构成逆序对数量:res += mid - i + 1;
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int temp[N];
long long find(int a[], int l, int r){
if(l >= r) return 0;
int mid = l + (r - l >> 1);
long long res = 0;
res += find(a, l, mid);
res += find(a, mid + 1, r);
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r){
if(a[i] <= a[j]) temp[k++] = a[i++];
else
{
temp[k++] = a[j++];
res += mid - i + 1;
}
}
while(i <= mid) temp[k++] = a[i++];
while(j <= r) temp[k++] = a[j++];
for(i = l,k = 0;i <= r;i++)
a[i] = temp[k++];
return res;
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n;i++){
cin >> a[i];
}
cout << find(a, 0 ,n - 1);
}
谢谢大佬的图解
瞬间思路开通了
我也是
我也是
“这是因为在合并过程中,如果左边的子数组元素 arr[i] 大于右边的子数组元素 arr[j],则 arr[i] 大于右边子数组中的所有元素,形成逆序对。”这句话是不是有点奇怪???
左边数组从小到大,右边数组从小到大,左边一个大于右边一个,怎么说,a【i】大于右边所有数?
应该不小心说错了吧😄
文字已经解释的很清楚了,比榜一解释的更好
谢谢大佬
请问大佬的动图是用什么做的呀
图怎么做的吖,想学
非常感谢,弄清思路后只需要在原来代码模板基础上加一行sum变量统计逆序对数就可以,再次感谢
谢谢大佬的思路,一开始想到了这题应该是要用归并排序然后进行判断,然后思路就卡住了,不知道下一步的做法,看了大佬得思路瞬间就通了。
似乎没写return 0;..................
这个不影响的,会自动补上
感谢 顿悟了
请问大佬们,只有图中最后一步合并的时候需要累加数字吗,把整个数组都分开以后逐步合并的过程里面的逆序对不用考虑是吗也就是y总说默认mergesort可以算出来的那部分怎么算的在哪体现的,是最后一步用排好序的归并就可以算出来所有的吗?谢谢大家
100000个的测试数据为什么结果为:
输出
28836452
标准答案
2499304400
但仍然能提交答案?
意思是调试的时候100000个的测试数据吗,调试的时候如果是这么多数据的话不会全部显示在网页上太多了,所以调试结果只有网页上那些的话肯定和正解是对不上的,只有提交进行真正那么多数据测试才可能和结果对的上
明白了,多谢
大佬这个图速度太快 我还没想理解呢 就一闪而过
可以下载下来,慢慢放