逆序对

简介

查找一个序列中的逆序对个数。

逆序对:如果i<j&&a[i]>a[j]则为一对逆序对。

朴素算法

暴力枚举每两个数并进行比较,如果符合i<j&&a[i]>a[j]则ans++。
时间复杂度: $O(n^2)$

归并排序

在归并排序的同时将逆序对求出。引用洛谷第一篇题解:
逆序对.PNG

#include<bits/stdc++.h>
using namespace std;
int a[500005];
int tmp[500005];
long long ans;
void merge(int l,int r){
    if(l==r){
        return ;
    }
    int mid=(l+r)/2;
    merge(l,mid);
    merge(mid+1,r);
    int ll=l,rr=mid+1;
    int cnt=l;
    while(ll<=mid&&rr<=r){
        if(a[ll]<=a[rr]){//这里是<=,逆序对不包含a[i]==a[j]的情况
            tmp[cnt]=a[ll];
            ll++;
            cnt++;
        }else{
            tmp[cnt]=a[rr];
            rr++;
            cnt++;
            ans+=mid-ll+1;
        }
    }
    while(ll<=mid){
        tmp[cnt]=a[ll];
        cnt++;
        ll++;
    }
    while(rr<=r){
        tmp[cnt]=a[rr];
        cnt++;
        rr++;
    }
    for(int i=l;i<=r;i++){
        a[i]=tmp[i];
    }
    return ;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    };
    merge(1,n);
    cout<<ans;
    return 0;
}

时间复杂度: $O(nlogn)$

在某博客上看到的诡异做法

把元素一个一个二分插入到一个有序vector数组中。然后ans加上插入位置前面的元素个数

#include<bits/stdc++.h>
using namespace std;
int a[500005];
vector<int> v;
int main(){
    int n,place;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        int place=upper_bound(v.begin(),v.end(),a[i])-v.begin();
        v.insert(v.begin()+now,a[i]);
        ans=ans+i-place-1;
        
    }
    cout<<ans<<endl;
    return 0;
}

时间复杂度: $O(nlogn)$

本文链接:http://kaispace.com.cn/index.php/archives/576/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者