题目描述:
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
输入:
每个测试案例包括两行:
第一行包含一个整数n,表示数组中的元素个数。其中1 <= n <= 10^5。
第二行包含n个整数,每个数组均为int类型。
输出:
对应每个测试案例,输出一个整数,表示数组中的逆序对的总数。
样例输入:
7 5 6 4
样例输出:
5
思路:最简单的方法是顺序数组,将每个数字与后面的比较,统计逆序对的个数,这种方法的时间复杂度为O(n*n),剑指offer给出了归并排序的思路,这个有点难想到啊,也可能是我太弱了,根本没往这方面想!理解了思路,就不难了,将子数数组划分成两个组,再将子数组分别划分成两个子数组,统计每个子数组内的逆序对个数,并将其归并排序,再统计两个子数组之间的逆序对个数,并进行归并排序。这就是归并排序的变种,在归并排序代码的基础上稍作改进即可。
合理还要注意一点:全局变量count不能声明为int型,必须为long long型。因为题目中说数组最大为10^5,那么最大逆序对为(10^5-1)*10^5/2,这个数大约在50亿左右,超过了int型的表示范围。
#include<stdio.h>
#include<stdlib.h>
int inversePairsCore(int*,int*,int,int);
int inversePairs(int *data,int length)
{
if(data==NULL||length==0)
return 0;
int *copy = new int[length];
for(int i=0;i<length;i++)
copy[i] = data[i];
int count=inversePairsCore(data,copy,0,length-1);
delete[] copy;
return count;
}
int inversePairsCore(int* data,int *copy,int start,int end)
{
if(start==end)
{
copy[start]=data[start];
return 0;
}
int length=(end-start)/2;
int left = inversePairsCore(copy,data,start,start+length);
int right = inversePairsCore(copy,data,start+length+1,end);
int i=start+length;
int j=end;
int indexCopy = end;
int count=0;
while(i>=start&&j>=start+length+1)
{
if(data[i]>data[j])
{
copy[indexCopy--]=data[i--];
count+=j-start-length;
}
else{
copy[indexCopy--]=data[j--];
}
}
for(;i>=start;--i)
copy[indexCopy--]=data[i];
for(;j>=start+length+1;--j)
copy[indexCopy--]=data[j];
return left+right+count;
}
int main()
{
int data[]={7,5,6,4};
int length=4;
int count = inversePairs(data,length);
printf("%d\n",count);
system("pause");
return 0;
}
分享到:
相关推荐
统计数组中的逆序对的个数,基于归并排序的思想,先拆分为单个元素,再合并为两个元素的数组,组内统计后,排序,进行组建统计
数组中的逆序对.md
数组中的逆序对在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。示例 1:输入: [7,5,6,4]输出: 5限制:0 数组
剑指Offer 51.数组中的逆序对(csdn)————程序
将一个数组逆序输出,用第一个与最后一个交换。 #!/usr/bin/python # -*- coding: UTF-8 -*- if __name__ == '__main__': a = [9,6,5,4,1] N = len(a) print a for i in range(len(a) / 2):
主要为大家详细介绍了java面试题之数组中的逆序对,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
广工《算法和高级数据结构教程》 逆序对(树状数组) c语言实现
C语言——借助指针实现数组元素的逆序.zip
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P00000007 输入描述: 题目保证输入的...
js代码-tmp-数组中的逆序对(结果对,超时)
js代码-tmp--数组中的逆序对-改
js代码-tmp-数组中的逆序对(wasted)
逆序数c++源码,直接运行
主要为大家详细介绍了java实现数组中的逆序对,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
剑指Offer(Python多种思路实现):数组中的逆序对 面试51题: 题目:数组中的逆序对 题目描述 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序...
有一实数序列a1,a2,....an,若i且ai>aj,则(ai,aj)形成了一个逆序对,请使用分治算法求整个序列中逆序对个数,并分析算法时间复杂度。
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P00000007 思路 根据题目描述可知,...
即输出P%1000000007输入描述:题目保证输入的数组中没有的相同的数字数据范围:对于%50的数据,size^4对于%75的数据,size^
主要为大家详细介绍了java简单实现数组中的逆序对,具有一定的参考价值,感兴趣的小伙伴们可以参考一下