逆序数及其求法
1. 逆序数
所谓逆序数，就是指⼀个序列S[i]，统计处于序列的每个数的⽐这个数⼤并且排在它前⾯的数的数⽬，然后对于所有数，把这个数⽬加起来求和就是了。
⽐如4 3 1 2
4第⼀个，所以数⽬为0
3的前⾯是4，⼤于3的数⽬为1
1的前⾯是4 3 ，⼤于1的数⽬为2
2的前⾯是4 3 1，⼤于2的数⽬为2
所以逆序数为1+2+2 = 5
求逆序数的两种⽅法
常规⽅法是按照逆序数的规则做，结果复杂度是O(n*n)，⼀般来说，有两种快速的求逆序数的⽅法
分别是归并排序和树状数组法
2. 归并排序
归并排序是源于分⽽治之思想，详细的过程可以查阅其他资料，总体思想是划分⼀半，各⾃排好序后将两个有序序列合并起来。
如何修改归并排序求逆序数?
⾸先我们假设两个有序序列a[i]和b[i]，当合并时：
由于a[i]已是有序，所以对于a[i]的各个元素来说，排在它前⾯且⽐它⼤的数⽬都是0
当b[i]中含有⽐a[i]⼩的元素时，我们必然将b[i]元素插到前⾯，那么就是说，在b[i]原先位置到该插的位置中，所有数都⽐b[i]⼤且排在它前⾯
所以这是b[i]的数⽬为新插⼊位置newPos - 原来位置oldPos
那么对于⼀半的序列⼜怎么做呢？我们知道，归并排序会继续向下递归，⽽递归完成返回后将是两组有序的序列，并且拿到局部的逆序数，
所以在Merge函数中添加这⼀计数操作即可
代码⽰例如下：
#include<stdio.h>
#define M 1000
int L[M];
int R[M];
const int Max = 1 <<30;
int change = 0;
void Merge(int *data,int left,int divide,int right)
{
int lengthL = divide - left;
merge函数int lengthR = right - divide;
for(int i = 0; i < lengthL; ++i)
{
L[i] = data[left + i];
}
for(int i = 0; i < lengthR; ++i)
{
R[i] = data[divide + i];
}
L[lengthL] = R[lengthR] = Max;
int i = 0;
int j = 0;
for(int k = left; k < right; ++k)
{
if(L[i] <= R[j])
{
data[k] = L[i];
++i;
}
else
{
change += divide - i - left ;
data[k] = R[j];
++j;
}
printf("%d ",data[k]);
}
printf("\n");
}
void MergeSort(int *data,int left,int right)
{
if(left < right -1)
{
int divide = (left + right)/2;
MergeSort(data,left,divide);
MergeSort(data,divide,right);
Merge(data,left,divide,right);
}
}
int main()
{
int n,i;
int map[100];
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&map[i]);
change=0;
MergeSort(map,0,n);
printf("%d\n",change);
}
return0;
}
View Code
3. 树状数组
求逆序数的另外⼀种⽅法是使⽤树状数组
对于⼩数据，可以直接插⼊树状数组，对于⼤数据，则需要离散化，所谓离散化，就是将
100 200 300 400 500 ---> 1 2 3 4 5
这⾥主要利⽤树状数组解决计数问题。
⾸先按顺序把序列a[i]每个数插⼊到树状数组中，插⼊的内容是1，表⽰放了⼀个数到树状数组中。
然后使⽤sum操作获取当前⽐a[i]⼩的数，那么当前i - sum则表⽰当前⽐a[i]⼤的数，如此反复直到所有数都统计完，⽐如
4 3 1 2
i = 1 : 插⼊4 : update(4,1)，sum(4)返回1，那么当前⽐4⼤的为i - 1 = 0;
i = 2 : 插⼊3 : update(3,1)，sum(3)返回1，那么当前⽐3⼤的为i - 1 = 1;
i = 3 : 插⼊1 : update(1,1)，sum(1)返回1，那么当前⽐1⼤的为i - 1 = 2;
i = 4 : 插⼊2 : update(2,1)，sum(2)返回2，那么当前⽐2⼤的为i - 2 = 2;
过程很明了，所以逆序数为1+2+2=5
代码⽰例如下：
//树状数组
__int64 sums[1005];
int len;
inline int lowbit(int t)
{
return t & (t^(t-1));
}
void update(int _x,int _value)
{
while(_x <= len)
{
sums[_x] += _value;
_x += lowbit(_x);
}
}
__int64 sum(int _end)//get sum[1_end] {
__int64 ret = 0;
while(_end > 0)
{
ret += sums[_end];
_end -= lowbit(_end);
}
return ret;
}
//求逆序数
__int64 ret = 0;
for (__int64 i = 0; i < k; ++i)
{
update(a[i],1);
ret += (i+1) - sum(a[i]);
}
求逆序数的题⽬有：
/problem?id=2299 /problem?id=3067

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。