基于分治法的特定数列逆序数求法
忙里偷闲,记录一下使用分治法求逆序数的实现过程。
算法设计
**逆序:**在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。例如<3,1>
就是一个逆序。
**逆序数:**给定数列中,逆序的数目。例如数列:
[1,3,4,2]
逆序数是2.
暴力法
很容易就想到的一个方法就是从头开始扫描,然后对于每一个扫描到的数字a
,考察后面的每一个数字b
,观察其是否满足逆序的定义,例如对于上述数列,对于数字1,逆序数为0;对于数字3,逆序数为1(<3,2>
),依此类推,最终数列总的逆序数为2.
很遗憾,该算法复杂度为$O(n^2)$,对于暴躁的张三来说,当其要计算长度为10000的数列的逆序数时候,他是无法接受长时间等待的,因为他还要去和阿珍约会呢
分治法
分而治之,逐个击破
分治法的思想是将原问题分解成若干个子问题,而所有的子问题进行简单处理后就可以得到原问题的解。求解子问题的过程亦可以继续分解成子子问题,而子问题分解到“原子问题”(原子问题好像也不太严谨,大概意思就是一个可以直接求解的问题)后可以立即得到解。
例如对于下面的数列:我们可以每次把子数列分成两半,分别求左半部分和右半部分的逆序数
那我们如何还原出原问题的解呢?即未分解问题时候的逆序数。仔细想想,我们已经计算出了左右两边逆序数leftCnt
、rightCnt
,那么我们再计算出在“ 一个数字取自左边,另一个数字取自右边”的情况下,逆序数cnt
的大小,原问题不就是这三个数字之和吗?
关键是怎么求cnt
?
老方法?依次从左边选一个数字a
,再依次从右边选一个数字b
,很抱歉,这样子下来要判断$\frac{n}{2}*\frac{n}{2}=\frac{n^2}{4} $次,综合下来时间复杂度还是$O(n^2)$。
仔细想想,我们要判断的数字一个来自左边,一个来自右边,如果我们分别让左边和右边有序,然后分别从第一个开始遍历,根据遍历到的数字进行计算逆序数,根据有序的性质,遍历完后逆序数也求解出来了,整个过程中,排序花费$O(n\log n)$,遍历花费$O(n)$,即合并子问题花费$O(n\log n)$.
关于合并过程的仔细分析,如下(简单起见,数列中不包含相同元素):
先将左右两部分排序,设置两个指针,分别从左右两部分进行遍历,设左边遍历得到的数字是a[i]
,右边的是b[j]
。
- 右边的指针j不断往后移动(尚未到结尾,如果到结尾,则到步骤3),直到
b[j]
恰好是右半部分中第一个不小于a[i]
的数字,即在右半部分中b[j]
的左边都是小于a[i]
的,此时,由a[i]
作为第一个数字组成的跨越左右两部分的数对(或者说序偶)中,逆序数刚好就是右半部分中b[j]
的左边的数字个数。说起来有点绕口,看看下面的图:
此时逆序数cnt
要加上n
.
- 左边的指针要往后移动,即指向
a[i+1]
,那么就会有两种情况:
- ①
a[i+1]>b[j]
:这个很好解决,继续回到步骤1即可。 - ②
a[i+1]<b[j]
:由于b[j]
的左边都是小于a[i]
,即存在这样的关系:b[j]>a[i+1]>a[i]>b[j-1]
,故此时由a[i+1]
作为第一个数字组成的跨越左右两部分的数对(或者说序偶)中,逆序数也是n
,此时逆序数cnt
要加上n
.下一步左边的指针要往后移动,继续步骤②,直到左边的指针指向元素比右边指针指向的大,回到步骤1,假若左边的指针先到了左半部分的最右边,则到步骤3。
- 此时要么左半部分先遍历完,要么右半部分先遍历完,假如是左边先遍历完,则说明此时“跨越左右两半部分的逆序数”统计完成,即
cnt
是正确的值,跳步骤4.如果是右半部分先遍历完成,则说明左边尚未遍历完成的数字都要比右半部分的数字大,根据这个条件计算逆序数后,转步骤4. - 将
leftCnt + rightCnt + cnt
作为原问题的解。
算法分析
下面进行时间复杂度分析,我们子问题个数是2(分别递归求解左右两个部分),每个子问题的规模是原来的一半,合并子问题花费$O(n\log n)$。
则: $$ T(n)=2T(\frac{n}{2} )+O(n \log n) $$ 根据主定理,得 $$ T(n)=O(n \log n) $$
算法实现
#include<iostream>
#include<algorithm>
using namespace std;
const int LEN = 100000 + 2;
int list[LEN], length;
long long reverseOrderNumber(int left, int right){
if (left >= right)return 0;
if (left + 1 == right)return list[left] > list[right];
int mid = (left + right) >> 1;
// 分别求解子问题
long long leftCnt = reverseOrderNumber(left, mid);
long long rightCnt = reverseOrderNumber(mid + 1, right);
// 排序左右两半部分
int *l1 = list + left, *r1 = list + mid - left + 1 + left;
sort(l1, r1);
sort(r1, list + right + 1);
// 计算跨左右部分的逆序数
int i = left, j = mid + 1;
long long cnt = 0;
while(i <= mid && j <= right){
// 在右边寻找第一个大于 a[i] 的元素
while(j <= right && list[i] > list[j])j++;
if (j > right)break;
while(i <= mid && list[i] < list[j]){
i++;
cnt += j - 1 - mid;
}
}
// 左边尚未遍历完的数字都要比右半部分的大
if(j > right) cnt += (mid - i + 1) * (right - mid);
// 合并子问题
return leftCnt + rightCnt + cnt;
}
int main(){
// printf("input the length:\n");
scanf("%d", &length);
// printf("input the value:\n");
for (int i = 0; i < length;i++)
scanf("%d", &list[i]);
printf("%lld\n", reverseOrderNumber(0, length - 1));
return 0;
}
/*
4
5 3 7 2
4
5 9 7 2
8
5 9 12 16 2 3 13 14
3
7 4 3
6
2 6 3 4 5 1
*/
实际上排序过程也可以使用归并排序,并且排序过程就可以计算逆序数了,不过归并排序过程要辅助空间,这里就没有采用。
本文由「黄阿信」创作,创作不易,请多支持。
如果您觉得本文写得不错,那就点一下「赞赏」请我喝杯咖啡~
商业转载请联系作者获得授权,非商业转载请附上原文出处及本链接。
关注公众号,获取最新动态!