逆序数的几种求法

淩亂°似流年 2022-08-07 10:56 421阅读 0赞

逆序数就是指比如：数组A=\{2,4,3,5\}那么<4,3>就是一个逆序数。

**一：暴力匹配**

对于数组A中的元素，i从0到n-1，j从i+1到n, 判断每一个是否为逆序数，时间复杂度O(N^2)。太简单了，没写代码了。。。。。

**二：归并**

归并排序能解决逆序数主要在于：比如归并A1=\{2,4,5\}, A2=\{1,3\}，进行归并的时候，我们每次判断A1和A2中元素大小，这里有两种思路：(1)当A1\[i\] <=A2\[j\]，此时需要放入A1\[i\]了，我们可以计算已经放入的A2中的元素个数即为j-mid-1；思路(2)当A1\[i\] <=A2\[j\]，我们不管它，直接放入即可，但当A1\[i\] >A2\[j\],此时需要放入A2\[j\]，我们来计算A1中还有多少个元素没有放mid – i+1，它们A2\[j\]所对应的逆序数个数。思路一对于归并算法有两处需要修改，思路二只需一处修改就可以了。时间复杂度为O(NlgN)

思路(1)代码：

void mergeSortInverseNumber(int a[], int p, int q, int a1[], long long int &number){
    	if(p < q){
    		int r = (p+q)/2;
    		mergeSortInverseNumber(a, p, r, a1, number);
    		mergeSortInverseNumber(a, r+1, q, a1, number);
    		int i = p, j = r+1;
    		int k = p;
    		while(i <= r && j <= q){
    			if(a[i] <= a[j]){
    				a1[k++] = a[i++];
    				number += j - r -1;    // 把a[i]放进来时 seq2中已有多少个数 就是逆序数
    			}
    			else
    				a1[k++] = a[j++];
    		}
    		if(i > r){
    			while(j <= q)
    				a1[k++] = a[j++];
    		}
    		else{
    			while(i <= r){
    				a1[k++] = a[i++];
    				number += j - r - 1;     这里也需要修改
    			}
    		}
    		for(int i = p; i <=q; i++)
    			a[i] = a1[i];
    	}
    }

思路(2)代码：

void mergeSortInverseNumber2(int a[], int p, int q, int a1[], long long int &number){
    	if(p < q){
    		int r = (p+q)/2;
    		mergeSortInverseNumber(a, p, r, a1, number);
    		mergeSortInverseNumber(a, r+1, q, a1, number);
    		int i = p, j = r+1;
    		int k = p;
    		while(i <= r && j <= q){
    			if(a[i] <= a[j])
    				a1[k++] = a[i++];
    				
    			else{
    				a1[k++] = a[j++];
    				number += r - i + 1;    // 把a[j]放进来时 seq1中还有多少个元素没有放入 就是逆序数
    			}
    		}
    		if(i > r){
    			while(j <= q)
    				a1[k++] = a[j++];
    		}
    		else{
    			while(i <= r)
    				a1[k++] = a[i++];
    			
    		}
    		for(int i = p; i <=q; i++)
    			a[i] = a1[i];
    	}
    }

**三：树状数组**

树状数组解法挺难理解的，我也还没有理解，也不需要理解。这里给出网上的一份代码：

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <algorithm>
    #include <string.h>
    using namespace std;
     
    const int maxn=500005;
    int n;
    int aa[maxn]; //离散化后的数组
    int c[maxn];    //树状数组
     
    struct Node{
       int v;
       int order;
    }in[maxn];
     
    int lowbit(int x)
    {
        return x&(-x);
    }
     
    void update(int t,int value)
    {
        int i;
        for(i=t;i<=n;i+=lowbit(i))
        {
            c[i]+=value;
        }
    }
     
    int getsum(int x)
    {
        int i;
        int temp=0;
        for(i=x;i>=1;i-=lowbit(i))
        {
            temp+=c[i];
        }
        return temp;
    }
     
    bool cmp(Node a ,Node b)
    {
        return a.v<b.v;
    }
     
    int main()
    {
        int i,j;
        while(scanf("%d",&n)==1 && n)
        {
            //离散化
            for(i=1;i<=n;i++)
            {
                scanf("%d",&in[i].v);
                in[i].order=i;
            }
            sort(in+1,in+n+1,cmp);
            for(i=1;i<=n;i++) aa[in[i].order]=i;
            //树状数组求逆序
            memset(c,0,sizeof(c));
            long long ans=0;
            for(i=1;i<=n;i++)
            {
                update(aa[i],1);
                ans+=i-getsum(aa[i]);
            }
            cout<<ans<<endl;
        }
        return 0;
    }

既然由前面一篇blog我们知道凡是树状数组能解决的问题，线段树都能解决，为什么不用线段树来解决呢？

**四：线段树**

线段树解决逆序数的思路是：设数组的大小为N，元素也都是1~N之间的元素，那么此时我们可以建立一棵\[1,N\]的线段树。遍历数组中的每个元素x时，我们需要查询线段树中\[x+1,N\]之间含有已插入元素的个数，并且更新线段树，将区间\[x,x\]及所有包含x的区间都加1。建立线段树为O(N),获得逆序数为O(lgN).

当然这里前提是元素大小都为1~N之间，那么如果不在这个区间怎么办呢，这时我们可以将离散的数据进行压缩。看以下代码：

// 离散化的数据进行压缩
    struct arrayExtend{
    	int val;
    	int index;
    };

int N;
    	cin >> N;
    	int *a = new int[N+1];
    	//  通过一个结构体将数据进行压缩 压缩分范围为1~N之间 顺序保持不变
    	arrayExtend *a1 = new arrayExtend[N+1];
    	for(int i = 1; i <= N; i++){
    		cin >> a1[i].val;
    		a1[i].index = i;
    	}
    	sort(a1+1, a1+N+1, cmp);  // 排序
    	a[a1[1].index] = 1;
    	for(int i = 2; i <= N; i++){
    		if(a1[i].val == a1[i-1].val){
    			a[a1[i].index] = a[a1[i-1].index];   // 相等的处理
    		}else
    			a[a1[i].index] = i;   // 不相等的处理
    	}

完整代码：

/*功能：线段树来求逆序数*/
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    #define MAXSIZE  100000
    #define M 300000
    
    // 离散化的数据进行压缩
    struct arrayExtend{
    	int val;
    	int index;
    };
    bool cmp(arrayExtend ae1, arrayExtend ae2){
    	return ae1.val < ae2.val;
    }
    
    // 线段树结点
    struct node{
    	int left, right, sum;
    }t[M];
    
    
    
    void build(int root, int start, int end){
    	//  如果相等 则为叶子结点 返回
    	if(start == end){
    		t[root].sum = 0;
    		t[root].left = start;
    		t[root].right = end;
    		return;
    	}
    	int mid = (start+end) >> 1;
    	build(root*2+1, start, mid);   // 创造左子树
    	build(root*2+2, mid+1, end);   // 创造右子树
    	t[root].sum = 0;
    	t[root].left = start;
    	t[root].right = end;
    }
    
    
    long long int getSum(int root, int qstart, int end){
    	if(qstart > end) return 0;
    	// 如果查询区间大于待查区间 则返回其值
    	if(t[root].left >= qstart && t[root].right <= end) return t[root].sum;
    	int mid = (t[root].left + t[root].right) >> 1;
    	if(qstart > mid) return getSum(root*2+2, qstart, end);
    	else return getSum(root*2+1, qstart, end) + getSum(root*2+2, qstart, end);
    }
    
    // 值为index 此时将包含index的区间sum+1 表示该区间有多少个数
    void update(int root, int index){
    	if(t[root].left == t[root].right){
    		t[root].sum += 1;
    		return;
    	}
    	int mid = (t[root].left + t[root].right) >> 1;
    	if(mid < index) update(root*2+2, index);
    	else update(root*2+1, index);
    	t[root].sum = t[root*2+1].sum + t[root*2+2].sum;   // 回溯
    }
    
    
    
    int main(){
    	int N;
    	cin >> N;
    	int *a = new int[N+1];
    	//  通过一个结构体将数据进行压缩 压缩分范围为1~N之间 顺序保持不变
    	arrayExtend *a1 = new arrayExtend[N+1];
    	for(int i = 1; i <= N; i++){
    		cin >> a1[i].val;
    		a1[i].index = i;
    	}
    	sort(a1+1, a1+N+1, cmp);  // 排序
    	a[a1[1].index] = 1;
    	for(int i = 2; i <= N; i++){
    		if(a1[i].val == a1[i-1].val){
    			a[a1[i].index] = a[a1[i-1].index];   // 相等的处理
    		}else
    			a[a1[i].index] = i;   // 不相等的处理
    	}
    
    	build(0, 1, N);
    	long long int ans = 0;
    	for(int i = 1; i<= N; i++){
    		ans += getSum(0, a[i]+1, N);    //  输入a[i]  即寻找【a[i]+1，N】之间元素个数
    		update(0, a[i]);         // 更新线段树
    	}
    	cout << ans << endl;
    
    	delete []a1;
    	delete []a;
    	return 0;
    }

注意存储一棵线段树所需要的结点树为满二叉树的结点个数为 2^(ceil(logN)+1)-1的个数。此外逆序数个数为long long 不然hihoCoder第三十九周只能得到80分。因为数据为10^5,逆序数个数可以达到5\*10^9, 而int大小只有4\*10^9多点。