求逆序数的多种解法

向右看齐 2022-07-14 00:44 360阅读 0赞

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

--------------------

思路1：暴力查询，双重for循环

for(i=1;i<=n;i++)  
for(j=i+1;j<=n;j++)  
if(a\[i\]>a\[j\])  
\{  
k++;  
\}

**如果数据吧比较多，更新和查找速度变得非常慢。**

--------------------

思路2：排序  
比如：2 4 3 1  
先查找最小的数1，在它前面有3个数据，全部都比他大，把这个1变成0  
再查找除去1最小的2，在它前面有0个数据比他大，然后把这个2变成0  
同理，查找3，他前面只有一个数据比他大（2已经变成0）  
所以，2 4 3 1这个数列的逆序数为3+0+1=4

**如果数据吧比较多，更新和查找会比较繁琐。**

--------------------

思路3：结构体排序  
比如：2 4 3 1  
**继续优化思路2：**  
2 4 3 1（a）  
1 1 1 1（b）  
现在只需要查找当前数列中最小的数，查找他之前有多少个1，然后把当前位置的1变成0

2 4 3 1  
1 1 1 1  
1 2 1 4  
**优化对1查找之后的累加**  
利用树状数组，数组b初始化为1，求b的树状数组的前n-1项和，也就是sum(n-1)或者sum(n)-1，然后把n的位置减去1，也就是change(n,-1);

每次查找当前数列最小值，数据多的时候，查找就不那么方便，所以，**我们利用结构体进行排序进行查找过程的优化**

利用 a\[\].val 记录数据  
利用 a\[\].id 记录位置  
2 4 3 1 （a.val）  
1 2 3 4 （a.id）  
进行排序之后变成  
1 2 3 4 （a.val）  
4 1 3 2 （a.id ）  
1 1 1 1 （ b ）

然后我们就可以从a.val的第一个开始查找，依次向后移动，我们利用a.id记录位置，去判断和求和；  
比如，我们去判断a.val中的1前面有几个数，就可以用树状数组的知识：sum(a.id)-1或者sum(a.id-1)；把1变成0可以用change(a.id,-1)；

--------------------

应用：  
51nod 逆序数:  
[http://www.51nod.com/onlineJudge/submitDetail.html\#!judgeId=171479][http_www.51nod.com_onlineJudge_submitDetail.html_judgeId_171479]

[http_www.51nod.com_onlineJudge_submitDetail.html_judgeId_171479]: http://www.51nod.com/onlineJudge/submitDetail.html#!judgeId=171479