前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数组中的逆序对

数组中的逆序对

作者头像
恋喵大鲤鱼
发布2018-08-03 15:19:41
9900
发布2018-08-03 15:19:41
举报
文章被收录于专栏:C/C++基础

题目: 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

解法一:暴力法 统计数组中的逆序对的逆序对,可以使用暴力的方法,即顺序扫描整个数组,每扫描到一个数字的时候,逐个与该数字后面的数字比较大小,如果大于后面的某个数字,则形成一个逆序对。

暴力法简单易懂,容易实现,但是其时间复杂度为O(n2)O(n^2)。

解法二:归并统计 借鉴归并排序的思想,将数组拆分成单个有序的字数组,再进行合并的过程中进行逆序对的统计。时间复杂度为O(nlogn)O(nlogn)。归并排序的实现见:归并排序实现

归并排序分为了2步骤; 第一步 数组拆分,直至规模较小的数组只含有一个元素; 第二步 合并两个已排好序的数组。

因此从整个数组拆分过程中,我们将它不断进行拆分,而拆分得到的两个数组,这样可以想到递归解决问题。

那么加入了逆序对后,如何考虑呢,实际上很简单。以从最下面的含一个元素的数组,到上层含多个元素的数组都有前后之分,这正好与逆序对性质相符,只要我们找出前面那一个数组中假设L[i] 大于后面一个数组中某个元素R[j],然后就知道前面那个数组在该元素L[i]之后的元素都应该是大于R[j]的。因为在归并过程我们也进行了排序。

参考代码:

代码语言:javascript
复制
#include <iostream>
using namespace std;

/*********************************
func:合并有序的相邻字数组,并统计逆序对数
para:a:左有序字数组;lenA:左有序字数组长度;b:右有序字数组;lenB:右有序字数组长度;inversePairsCount:相邻有序字数组a和b之间存在的逆序对数
return:void
*********************************/
void mergeAndCount(int* a,int lenA,int* b,int lenB,int& inversePairsCount){
    int* temp=new int[lenA+lenB];
    int index=0;
    memset(temp,0,sizeof(int)*(lenA+lenB));
    int* aPtr=a;
    int* bPtr=b;
    while(aPtr<a+lenA&&bPtr<b+lenB){
        if(*aPtr<=*bPtr){
            temp[index++]=*(aPtr++);
        }
        else{ //A大于B的元素,将B的元素与A的当前及后面的元素比较大小,判断逆序对数
            for(int* aNow=aPtr;aNow<a+lenA;++aNow){
                if(*aNow>*bPtr)
                    ++inversePairsCount;
            }
            temp[index++]=*(bPtr++);
        }
    }
    while(aPtr<a+lenA)
        temp[index++]=*(aPtr++);
    while(bPtr<b+lenB)
        temp[index++]=*(bPtr++);
    memcpy(a,temp,sizeof(int)*(lenA+lenB));
    delete[] temp;
}

/*******************************************
func:统计给定数组A中存在逆序对数
para:A:待统计数组;len:数组A的长度;inversePairsCount:逆序对数
ret:void
*******************************************/
void inverseCount(int A[],int len,int& inversePairsCount){
    int leftLen=len/2;
    if(leftLen>0){
        inverseCount(A,leftLen,inversePairsCount);
        inverseCount(A+leftLen,len-leftLen,inversePairsCount);
        mergeAndCount(A,leftLen,A+leftLen,len-leftLen,inversePairsCount);
    }
}

int main(){
    int A[]={7,5,6,4,1};
    int inversePairsCount=0;
    inverseCount(A,5,inversePairsCount);
    cout<<"inversePairsCount:"<<inversePairsCount<<endl;
    for(int i=0;i<5;++i)
        cout<<A[i]<<" ";
    getchar();
}

结果输出:


参考文献

[1]剑指Offer.何海涛.电子工业出版社.

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016年03月30日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 参考文献
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档