博客

算法：求逆序对个数

Description

有一实数或者字母序列A[1]、A[2] 、A[3] 、……A[n-1] 、A[n]，若i＜j，并且A[i]＞A[j]，则称A[i]与A[j]构成了一个逆序对，求字符串A中逆序对的个数。要求时间复杂度为O(nlogn)

Input

输入包括多个测试数据，每一行为一个，每个测试数据长度不超过50000。

Output

输出每个数据的逆序对个数。

结合目前所学知识可以采用以下四种方式来解决：

1：暴力跑数据

2：归并排序

3：数据结构加离散化

4：权值线段树

法一：暴力硬怼

从前往后依次比较，前边比后边大则加一。

#include<iostream>
using namespace std;
#include<stdio.h>
#include<string.h>
int main()
{
    char s[50001];
    while(scanf("%s",&s)!=EOF)
    {
        int js=0;
        for(int i=0;i<=strlen(s)-1;i++)
            for(int j=i+1;j<=strlen(s)-1;j++)
            {
                js+=s[i]>s[j]?1:0;
            }
            cout<<js<<endl;
    }
}

方法二


归并排序

原理是利用排好序的两个数组在归并过程中计算区间中点与前一个数组之间的距离，因为在这个过 程中，前一个数组是已经排好序的，所以这个距离就是前边数组中的元素比后边那个数组当前那一位大的元素个数，即在这一次的归并过程中需要增加的逆序对的个数。时间复杂度为nlogn.

#include<iostream>
using namespace std;
const int maxn=1e6+10;

int n,a[maxn];
long long ans;

//归并排序
int temp[maxn];
void merge_sort(int l,int r)
{
    if(l==r)
        return;
    int mid=l+r>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int ll=l,sst=l,sse=r,rr=mid+1;
    while(l<=mid and rr<=r)
    {
        if(a[l]<=a[rr])
            temp[ll++]=a[l++];
        else
        {
            temp[ll++]=a[rr++],ans+=mid-l+1;
            //cout<<mid-l+1<<" "<<sst<<" "<<sse<<endl;
            /*8
            5 2 4 6 2 3 2 6*/
        }
    }
    while(l<=mid)
        temp[ll++]=a[l++];
    while(rr<=r)
        temp[ll++]=a[rr++];
    for(int i=sst; i<=r; i++)
        a[i]=temp[i];
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    merge_sort(1,n);
    cout<<ans<<endl;
    return 0;
}

方法三


：树状数组加离散化

先将给定的数组离散化成对应的1-n的数组，然后将该数组进行树状数组的查询与修改操作，每次查询需要查询出小于该数的数字求和，然后将该数添加到该数组中对应的每个节点只需进行加一操作，将离散化的数组全部从后往前依次进行查找与修改操作即可得到逆序对。时间复杂度为nlogn.默认常数最小。

#include<iostream>
#include<algorithm>
using namespace std;
int a[100005];
int b[100005];
int tree[100005];
int n;

bool cmp(int x,int y)
{
    return a[x]<a[y];
}

int lowbit(int x)
{
    return x&(-x);
}

void add(int x)
{
    while(x<=n)
    {
        tree[x]++;//节点加一
        x+=lowbit(x);
    }
}

long long query(int pos)
{
    long long ans=0;
    while(pos>0)
    {
        ans+=tree[pos];//区间求和
        pos-=lowbit(pos);
    }
    return ans;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=i;
    }
    sort(b+1,b+n+1,cmp);
    long long sum=0;
    for(int i=1;i<=n;i++)
    {
        a[b[i]]=i;
    }
    for(int i=n;i>=1;i--)
    {
        sum+=query(a[i]-1);
        add(a[i]);
    }
    cout<<sum;
}

方法四


：权值线段树

线段树操作方式：


单点修改，区间查询。

单点修改：每次将该数在线段树中对应下标加一。

区间查询：每次将x+1到maxn全部求和，既是在数组中该书前边全部比他大的数，即该点的逆序对数。时间复杂度为nlogn.

#include<iostream>
using namespace std;
const int maxn=1e6+10;

int n,a[maxn];
long long ans;

//权值线段树
struct
{
    int l,r,tot;
} e[maxn*4];

void build(int k,int l,int r)
{
    e[k].l=l,e[k].r=r;
    if(l==r)
        return;
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}

void update(int k,int num)
{
    if(e[k].l==num && e[k].r==num)
    {
        e[k].tot++;
        return;
    }
    int mid=(e[k].l+e[k].r)>>1;
    if(num<=mid)
        update(k<<1,num);
    if(num>mid)
        update(k<<1|1,num);
    e[k].tot=e[k<<1].tot+e[k<<1|1].tot;
    return;
}

long long sum(int k,int l,int r)
{
    if(e[k].l>r or e[k].r<l)
        return 0;
    if(e[k].l==l and e[k].r==r)
        return e[k].tot;
    int mid=e[k].l+e[k].r>>1;
    if(mid>=r)
        return sum(k<<1,l,r);
    if(mid<l)
        return sum(k<<1|1,l,r);
    return sum(k<<1,l,mid)+sum(k<<1|1,mid+1,r);
}


int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    build(1,1,maxn);
    for(int i=1; i<=n; i++)
    {
        ans+=sum(1,a[i]+1,maxn);
        update(1,a[i]);
    }
    cout<<ans<<endl;
    return 0;
}