[编程题]数组中的逆序对
- 热度指数：561455 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。
即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
示例1
输入
1,2,3,4,5,6,7,0
输出
7
思路分析：
看到这个题目，我们的第一反应是顺序扫描整个数组。每扫描到一个数组的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成了一个逆序对。假设数组中含有n个数字。由于每个数字都要和O(n)这个数字比较，因此这个算法的时间复杂度为O(n^2)。
我们以数组{7,5,6,4}为例来分析统计逆序对的过程。每次扫描到一个数字的时候，我们不拿ta和后面的每一个数字作比较，否则时间复杂度就是O(n^2)，因此我们可以考虑先比较两个相邻的数字。
(a) 把长度为4的数组分解成两个长度为2的子数组；
(b) 把长度为2的数组分解成两个成都为1的子数组；
(c) 把长度为1的子数组 合并、排序并统计逆序对 ；
(d) 把长度为2的子数组合并、排序，并统计逆序对；
在上图（a）和（b）中，我们先把数组分解成两个长度为2的子数组，再把这两个子数组分别拆成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5，因此（7,5）组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对（6,4）。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组 排序 如上图（c）所示， 以免在以后的统计过程中再重复统计。
接下来我们统计两个长度为2的子数组子数组之间的逆序对。合并子数组并统计逆序对的过程如下图如下图所示。
我们先用两个指针分别指向两个子数组的末尾，并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个数组中的数字，则构成逆序对，并且逆序对的数目等于第二个子数组中剩余数字的个数，如下图（a）和（c）所示。如果第一个数组的数字小于或等于第二个数组中的数字，则不构成逆序对，如图b所示。每一次比较的时候，我们都把较大的数字从后面往前复制到一个辅助数组中，确保 辅助数组（记为copy） 中的数字是递增排序的。在把较大的数字复制到辅助数组之后，把对应的指针向前移动一位，接下来进行下一轮比较。
过程：先把数组分割成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。如果对排序算法很熟悉，我们不难发现这个过程实际上就是归并排序。参考代码如下：
class Solution {
public:
int InversePairs(vector<int> data) {
int length=data.size();
if(length<=0)
return 0;
//vector<int> copy=new vector<int>[length];
vector<int> copy;
for(int i=0;i<length;i++)
copy.push_back(data[i]);
long long count=InversePairsCore(data,copy,0,length-1);
//delete[]copy;
return count%1000000007;
}
long long InversePairsCore(vector<int> &data,vector<int> ©,int start,int end)
{
if(start==end)
{
copy[start]=data[start];
return 0;
}
int length=(end-start)/2;
long long left=InversePairsCore(copy,data,start,start+length);
long long right=InversePairsCore(copy,data,start+length+1,end);
int i=start+length;
int j=end;
int indexcopy=end;
long long count=0;
while(i>=start&&j>=start+length+1)
{
if(data[i]>data[j])
{
copy[indexcopy--]=data[i--];
count=count+j-start-length; //count=count+j-(start+length+1)+1;
}
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;
}
};
编辑于 2018-05-04 10:25:36
回复(94)
count = 0 class Solution: def InversePairs(self, data): global count def MergeSort(lists): global count if len(lists) <= 1: return lists num = int( len(lists)/2 ) left = MergeSort(lists[:num]) right = MergeSort(lists[num:]) r, l=0, 0 result=[] while l<len(left) and r<len(right): if left[l] < right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 count += len(left)-l result += right[r:] result += left[l:] return result MergeSort(data) return count%1000000007
个人PC上500ms内，牛客网就超时了，python本来就慢。归并算法内计数，Python2 没有nonlocal挺蛋疼的。
编辑于 2017-07-11 20:28:59
回复(23)
/*归并排序的改进，把数据分成前后两个数组(递归分到每个数组仅有一个数据项)，
合并数组，合并时，出现前面的数组值array[i]大于后面数组值array[j]时；则前面
数组array[i]~array[mid]都是大于array[j]的，count += mid+1 - i
参考剑指Offer，但是感觉剑指Offer归并过程少了一步拷贝过程。
还有就是测试用例输出结果比较大，对每次返回的count mod(1000000007)求余
*/
public class Solution {
public int InversePairs(int [] array) {
if(array==null||array.length==0)
{
return 0;
}
int[] copy = new int[array.length];
for(int i=0;i<array.length;i++)
{
copy[i] = array[i];
}
int count = InversePairsCore(array,copy,0,array.length-1);//数值过大求余
return count;
}
private int InversePairsCore(int[] array,int[] copy,int low,int high)
{
if(low==high)
{
return 0;
}
int mid = (low+high)>>1;
int leftCount = InversePairsCore(array,copy,low,mid)%1000000007;
int rightCount = InversePairsCore(array,copy,mid+1,high)%1000000007;
int count = 0;
int i=mid;
int j=high;
int locCopy = high;
while(i>=low&&j>mid)
{
if(array[i]>array[j])
{
count += j-mid;
copy[locCopy--] = array[i--];
if(count>=1000000007)//数值过大求余
{
count%=1000000007;
}
}
else
{
copy[locCopy--] = array[j--];
}
}
for(;i>=low;i--)
{
copy[locCopy--]=array[i];
}
for(;j>mid;j--)
{
copy[locCopy--]=array[j];
}
for(int s=low;s<=high;s++)
{
array[s] = copy[s];
}
return (leftCount+rightCount+count)%1000000007;
}
}
编辑于 2016-08-02 10:31:03
回复(93)
public class Solution {
int cnt;
public int InversePairs(int[] array) {
cnt = 0;
if (array != null)
mergeSortUp2Down(array, 0, array.length - 1);
return cnt;
}
/*
* 归并排序(从上往下)
*/
public void mergeSortUp2Down(int[] a, int start, int end) {
if (start >= end)
return;
int mid = (start + end) >> 1;
mergeSortUp2Down(a, start, mid);
mergeSortUp2Down(a, mid + 1, end);
merge(a, start, mid, end);
}
/*
* 将一个数组中的两个相邻有序区间合并成一个
*/
public void merge(int[] a, int start, int mid, int end) {
int[] tmp = new int[end - start + 1];
int i = start, j = mid + 1, k = 0;
while (i <= mid && j <= end) {
if (a[i] <= a[j])
tmp[k++] = a[i++];
else {
tmp[k++] = a[j++];
cnt += mid - i + 1; // core code, calculate InversePairs............
}
}
while (i <= mid)
tmp[k++] = a[i++];
while (j <= end)
tmp[k++] = a[j++];
for (k = 0; k < tmp.length; k++)
a[start + k] = tmp[k];
}
}
发表于 2016-03-07 21:18:57
回复(72)
//大家好，我是yishuihan
/*参考《剑指offer》，有两种思路。第一就是暴力求解法，时间复杂度为o（n^2）,空间复杂度o(1)
第二种思路就是使用归并排序的思想进行处理，时间复杂度o(nlog(n)),空间复杂度0（n）*/
class Solution {
public:
int InversePairs(vector<int> data) {
if(data.size()<=1) return 0;//如果少于等于1个元素，直接返回0
int* copy=new int[data.size()];
//初始化该数组，该数组作为存放临时排序的结果，最后要将排序的结果复制到原数组中
for(unsigned int i=0;i<data.size();i++)
copy[i]=0;
//调用递归函数求解结果
int count=InversePairCore(data,copy,0,data.size()-1);
delete[] copy;//删除临时数组
return count;
}
//程序的主体函数
int InversePairCore(vector<int>& data,int*& copy,int start,int end)
{
if(start==end)
{
copy[start]=data[start];
return 0;
}
//将数组拆分成两部分
int length=(end-start)/2;//这里使用的下标法，下面要用来计算逆序个数；也可以直接使用mid=（start+end）/2
//分别计算左边部分和右边部分
int left=InversePairCore(data,copy,start,start+length)%1000000007;
int right=InversePairCore(data,copy,start+length+1,end)%1000000007;
//进行逆序计算
int i=start+length;//前一个数组的最后一个下标
int j=end;//后一个数组的下标
int index=end;//辅助数组下标，从最后一个算起
int count=0;
while(i>=start && j>=start+length+1)
{
if(data[i]>data[j])
{
copy[index--]=data[i--];
//统计长度
count+=j-start-length;
if(count>=1000000007)//数值过大求余
count%=1000000007;
}
else
{
copy[index--]=data[j--];
}
}
for(;i>=start;--i)
{
copy[index--]=data[i];
}
for(;j>=start+length+1;--j)
{
copy[index--]=data[j];
}
//排序
for(int i=start; i<=end; i++) {
data[i] = copy[i];
}
//返回最终的结果
return (count+left+right)%1000000007;
}
};
编辑于 2016-08-05 11:33:29
回复(9)
题目描述
解题思路
这个之前的笔记中已经说过这道题目了，是归并排序的典型应用。归并排序的基本思想是分治，在治的过程中有前后数字的大小对比，此时就是统计逆序对的最佳时机。
我的答案
public class Solution {
//统计逆序对的个数
int cnt;
public int InversePairs(int [] array) {
if(array.length != 0){
divide(array,0,array.length-1);
}
return cnt;
}
//归并排序的分治---分
private void divide(int[] arr,int start,int end){
//递归的终止条件
if(start >= end)
return;
//计算中间值，注意溢出
int mid = start + (end - start)/2;
//递归分
divide(arr,start,mid);
divide(arr,mid+1,end);
//治
merge(arr,start,mid,end);
}
private void merge(int[] arr,int start,int mid,int end){
int[] temp = new int[end-start+1];
//存一下变量
int i=start,j=mid+1,k=0;
//下面就开始两两进行比较，若前面的数大于后面的数，就构成逆序对
while(i<=mid && j<=end){
//若前面小于后面，直接存进去，并且移动前面数所在的数组的指针即可
if(arr[i] <= arr[j]){
temp[k++] = arr[i++];
}else{
temp[k++] = arr[j++];
//a[i]>a[j]了，那么这一次，从a[i]开始到a[mid]必定都是大于这个a[j]的，因为此时分治的两边已经是各自有序了
cnt = (cnt+mid-i+1)%1000000007;
}
}
//各自还有剩余的没比完，直接赋值即可
while(i<=mid)
temp[k++] = arr[i++];
while(j<=end)
temp[k++] = arr[j++];
//覆盖原数组
for (k = 0; k < temp.length; k++)
arr[start + k] = temp[k];
}
}
编辑于 2019-03-10 14:31:16
回复(8)
# -*- coding:utf-8 -*- class Solution: def InversePairs(self, data): # write code here count = 0 copy = [] for i in data: copy.append(i) copy.sort() for i in range(len(copy)): count += data.index(copy[i]) data.remove(copy[i]) return count%1000000007 #我惊呆了，就是通不过，这没多复杂吧我的哥
发表于 2017-12-29 21:12:14
回复(15)
略微修改了书上的思路，直接归并将序排列，这样可以从头开始比较。其余思路一样
class Solution {
public:
long countRes ;
int InversePairs(vector<int> data) {
countRes = 0;
if(data.size() == 0)
return 0;
MergeSort(data,0,data.size()-1);
return countRes%1000000007 ;
}
void MergeSort(vector<int>& data,int first,int end){
if(first < end){
int mid = (first + end)/2;
MergeSort(data,first,mid);
MergeSort(data,mid+1,end);
vector<int> tmp;
MergeArray(data,first,mid,end,tmp);
}
}
void MergeArray(vector<int>& data,int first,int mid,int end,vector<int> tmp){
int i = first;int m = mid;
int j = mid + 1;int n = end;
while(i<=m && j<=n){
if(data[i] > data[j]){
tmp.push_back(data[i++]);
countRes += n - j + 1;
}
else{
tmp.push_back(data[j++]);
}
}
while(i<=m)
tmp.push_back(data[i++]);
while (j<=n)
tmp.push_back(data[j++]);
//更新data数组
int k = 0;
for (int i = first; i <= end &&k<tmp.size(); i++)
data[i] = tmp[k++];
}
};
编辑于 2016-07-19 19:34:19
回复(6)
参考《剑指offer》用归并排序的思想， 时间复杂度O(nlogn)
代码如下：
int InversePairs(vector<int> data) {
int length = data.size();
return mergeSort(data, 0, length-1);
}
int mergeSort(vector<int>& data, int start, int end) {
// 递归终止条件
if(start >= end) {
return 0;
}
// 递归
int mid = (start + end) / 2;
int leftCounts = mergeSort(data, start, mid);
int rightCounts = mergeSort(data, mid+1, end);
// 归并排序，并计算本次逆序对数
vector<int> copy(data); // 数组副本，用于归并排序
int foreIdx = mid; // 前半部分的指标
int backIdx = end; // 后半部分的指标
int counts = 0; // 记录本次逆序对数
int idxCopy = end; // 辅助数组的下标
while(foreIdx>=start && backIdx >= mid+1) {
if(data[foreIdx] > data[backIdx]) {
copy[idxCopy--] = data[foreIdx--];
counts += backIdx - mid;
} else {
copy[idxCopy--] = data[backIdx--];
}
}
while(foreIdx >= start) {
copy[idxCopy--] = data[foreIdx--];
}
while(backIdx >= mid+1) {
copy[idxCopy--] = data[backIdx--];
}
for(int i=start; i<=end; i++) {
data[i] = copy[i];
}
return (leftCounts+rightCounts+counts);
}
发表于 2015-08-29 14:13:14
回复(17)
class Solution {
public:
int InversePairs(vector<int> data) {
if(data.size()==0)
return 0;
vector<int> copy(data); // 辅助数组，每次递归后有序
return InversePairsCore(data, copy, 0, data.size()-1);
}
int InversePairsCore(vector<int>& data, vector<int>& copy, int begin, int end) {
if(begin == end)
return 0;
int mid = begin + (end-begin)/2;
int left = InversePairsCore(copy, data, begin, mid);
int right = InversePairsCore(copy, data, mid+1, end);
int last_in_left = mid; // 比较从尾端开始
int last_in_right = end; // 比较从尾端开始
int index_copy = end; // 比较结果存入辅助数组尾端
long res = 0;
// 归并排序：相当于两个有序数组合成一个有序表（从尾端开始是为了计数）
while(last_in_left>=begin && last_in_right>=mid+1) {
if(data[last_in_left] > data[last_in_right]) {
copy[index_copy--] = data[last_in_left--];
res += last_in_right - mid;
}
else
copy[index_copy--] = data[last_in_right--];
}
while(last_in_left >= begin)
copy[index_copy--] = data[last_in_left--];
while(last_in_right >= mid+1)
copy[index_copy--] = data[last_in_right--];
return (left+right+res) % 1000000007;
}
};
发表于 2017-07-26 21:51:02
回复(5)
//这道题debug了好久才提交，总是出现各种问题，得到了很多教训，如注释中的1,2,3
//另外debug时，不仅要观察最后的结果，还要看数组是否真的排序了
class Solution {
public:
int InversePairs(vector<int> data) {
//用long long类型否则会超限
long long num = 0;
mergesort(data, num, data.begin(), data.end() - 1);
return num%1000000007;
}
//归并排序
void mergesort(vector<int> &data, long long &num, vector<int>::iterator start, vector<int>::iterator end) {
if (start == end) return;
vector<int>::iterator mid = start + (end - start) / 2;
mergesort(data, num, start, mid);
mergesort(data, num, mid + 1, end);
merge(data, num, start, end);
}
//合并
void merge(vector<int> &data, long long &num, vector<int>::iterator start, vector<int>::iterator end) {
if (start == end) return;
vector<int>::iterator mid = start + (end - start) / 2;
//把要合并的两个子数组保存出来
vector<int> data1(start, mid+1);
vector<int> data2(mid + 1, end+1);
//两个迭代器分别指向两个数组的末尾
vector<int>::iterator p = data1.end() - 1;
vector<int>::iterator q = data2.end() - 1;
vector<int>::iterator m = end;
int sz1 = data1.size();
int sz2 = data2.size();
//合并，当前面数组的元素大于后面时计数加一
while (sz1>0&&sz2>0) {
if (*q<*p) {
num = q - data2.begin()+ 1+num;//1、迭代器相减注意顺序
*m = *p;
--sz1;
--m;
if(sz1>0) --p;//2、有效迭代器的范围是[begin(),end())，begin()位置已经不可以再自减了
}
else {
*m = *q;
--sz2;
--m;
if(sz2>0) --q;
}
}
//3、把剩余的放入数组中，一开始分析出来其中一个数组最多只剩一个元素，而没有让迭代器自减
while (sz1--) {
*m = *p;
if (sz1 > 0) {
--m;
--p;
}
}
while (sz2--) {
*m = *q;
if (sz2 > 0) {
--m;
--q;
}
}
}
};
发表于 2017-06-11 13:39:28
回复(0)
代码参考剑指offer
----------------------------------------------------------------
2016.08.02更新
class Solution {
public:
long long InversePairsCore(vector<int> &data,vector<int>©,int start,int end)
{
if(start==end)
{
copy[start]=data[start];
return 0;
}
int length = (end-start)/2;
long long left = InversePairsCore(copy,data,start,start+length);
long long right = InversePairsCore(copy,data,start+length+1,end);
int i = start + length;
int j = end;
int indexCopy = end;
long long 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 InversePairs(vector<int> data) {
int length = data.size();
if(length<=0)
return 0;
vector<int> copy;
for(int i=0;i<length;i++)
copy.push_back(data[i]);
long long count = InversePairsCore(data,copy,0,length-1);
copy.clear();
return count%1000000007;
}
};
编辑于 2016-08-02 17:21:55
回复(12)
/*
*归并排序的思想，最后求得的逆序数进行取摸 % 1000000007
*/
public class Solution {
public int InversePairs(int [] array) {
if(array==null || array.length<=0){
return 0;
}
int pairsNum=mergeSort(array,0,array.length-1);
return pairsNum;
}
public int mergeSort(int[] array,int left,int right){
if(left==right){
return 0;
}
int mid=(left+right)/2;
int leftNum=mergeSort(array,left,mid);
int rightNum=mergeSort(array,mid+1,right);
return (Sort(array,left,mid,right)+leftNum+rightNum)%1000000007;
}
public int Sort(int[] array,int left,int middle,int right){
int current1=middle;
int current2=right;
int current3=right-left;
int temp[]=new int[right-left+1];
int pairsnum=0;
while(current1>=left && current2>=middle+1){
if(array[current1]>array[current2]){
temp[current3--]=array[current1--];
pairsnum+=(current2-middle); //这个地方是current2-middle！！！！
if(pairsnum>1000000007)//数值过大求余
{
pairsnum%=1000000007;
}
}else{
temp[current3--]=array[current2--];
}
}
while(current1>=left){
temp[current3--]=array[current1--];
}
while(current2>=middle+1){
temp[current3--]=array[current2--];
}
//将临时数组赋值给原数组
int i=0;
while(left<=right){
array[left++]=temp[i++];
}
return pairsnum;
}
}
发表于 2016-07-28 19:53:04
回复(7)
class Solution: def InversePairs(self, data): #发现可以用归并排序，归并拼接后用计算排序时元素的index变动了多少 #两个有序序列，每个元素移动index数（严格来说不是移动，这里不知怎么表达）之和好像刚好等于逆序对的个数 #我也不知为什么，找了半天发现了这个规律 _,s=self.MergeSort(data) return s%1000000007 def MergeSort(self,data): n=len(data) #递归基 if n==1:return data, 0 #分两半来排序 part1,part2=data[:n//2],data[n//2:] sorted_part1,s1=self.MergeSort(part1) sorted_part2,s2=self.MergeSort(part2) #排序后拼接这两半，拼接后先计数，然后将两个有序序列合并 s,sorted_temp=0,sorted_part1+sorted_part2 #用p、q两个指针指向两段，计算q中每个元素离插入点的index差 p,q,len1,len_all=0,sorted_temp.index(sorted_part2[0]),len(sorted_part1),len(sorted_temp) while p<len1 and q<len_all: #移动p使p成为插入排序的插入点，计算要移动多少个位置 while p<len1: if sorted_temp[q]<sorted_temp[p]: s+=len1-p break p+=1 q+=1 #完成排序，并把排序后的内容回溯给上一级做准备 l=[] p,q=0,sorted_temp.index(sorted_part2[0]) while p<len1 and q<len_all: if sorted_temp[p]<sorted_temp[q]: l.append(sorted_temp[p]) p+=1 else: l.append(sorted_temp[q]) q+=1 if p==len1:l+=sorted_temp[q:] if q==len_all:l+=sorted_part1[p:] return l,s+s1+s2
嗯？貌似应该是剑指里的最难题。一开始用暴力的)
方法是不能通过的，思路想了很久，毕竟和顺序有关，就考虑了下排序，觉得就归并会有地方发挥，手动模拟了下果然也可以，于是就用归并了。通过后刚也进来看了下答案，挺有成就感的。这次的复杂度))
，在自己电脑这边弄到几千个数都能短时间内跑出来
另外说下就是，python判题时间似乎不够，我第一次是运气好才通过，后来试了好几次都超时，然后才通过第二次。感觉这个判题时间有点迷。一次不行多试几次就好了
编辑于 2019-03-16 17:12:02
回复(0)
这道题有毒，用python，就算是直接return 2519，也会是超时...
def InversePairs(self, data): # write code here # # import pdb # pdb.set_trace() res = 2519 #res = self.merge_sort(0, len(self.data) - 1) return res
发表于 2018-02-10 15:04:32
回复(7)
//运行时间296ms 内存5361k 第一次接触归并排序思想 学习了 参考大神的
//我是菜鸟我怕谁 QAQ
int count=0;
public int InversePairs(int [] array) {
if(array==null||array.length<=0) return 0;
mergeUp2Down(array,0,array.length-1);
return count;
}
public void mergeUp2Down(int [] a,int start,int end){
if(start>=end) return;
int mid=(end+start)>>1;
mergeUp2Down(a,start,mid);
mergeUp2Down(a,mid+1,end);
merge(a,start,mid,end);
}
public void merge(int [] a,int start,int mid,int end){
int[] temp=new int[end-start+1];
int i=start,j=mid+1,index=0;
while(i<=mid&&j<=end){
if(a[i]>a[j]) {
temp[index++]=a[j++];
count+=mid-i+1;
count=count>1000000007?count%1000000007:count;
}else temp[index++]=a[i++];
}
while(i<=mid) temp[index++]=a[i++];
while(j<=end) temp[index++]=a[j++];
for(int k=0;k<temp.length;k++) a[start+k]=temp[k];
}
编辑于 2017-05-09 02:42:51
回复(3)
感谢测试君更新了一下数据哈~
这个数据范围就正常多了。其实这个题目是可以有重复数字的，答案也在long long范围内(n*(n+1)/2)。
原来不离散化用map的已经超时了，所以还是老老实实离散化了，当然归并排序的方法就不用了。
O(n*log(n))
#define lb(x) ((x) & -(x))
typedef long long ll;
classBIT{
public:
intn;
vector<int> a;
BIT(intn) : n(n), a(n + 1, 0){}
voidadd(inti, intv){
for(; i <= n; i += lb(i)) a[i] += v;
}
ll sum(inti){
intr = 0;
for(; i; i -= lb(i)) r += a[i];
returnr;
}
};
classSolution {
public:
intInversePairs(vector<int> d) {
intn = d.size();
vector<int> t(d);
sort(t.begin(), t.end()); //排序
t.erase(unique(t.begin(), t.end()), t.end()); //去除重复元数（当然这题没有重复元素）
for(inti = 0; i < n; ++i) //离散化
d[i] = lower_bound(t.begin(), t.end(), d[i]) - t.begin() + 1;
BIT bit(t.size());
ll ans = 0;
for(inti = n - 1; i >= 0; --i){
ans += bit.sum(d[i] - 1);
bit.add(d[i], 1);
}
returnans % 1000000007;
}
};
=============================================
UPD: 看到有人用个数组暴力维护了大于0-8的数。。。原来数据才个位数啊。。。。我一口老血喷了出来，不做了，睡觉！
=============================================
经典问题，可以用归并排序（分治）或数状数组维护一下
数据这么小我也懒得离散化了，，直接用个map....（一脸紧张
#define lb(x) ((x) & -(x))
class BIT{
int n;
map<int, int> d;
public:
BIT(int n_) : n(n_) {}
void add(int i, int v){
for(; i <= n; i += lb(i)) d[i] += v;
}
int sum(int i){
int r = 0;
for(; i; i -= lb(i)) r += d[i];
return r;
}
};
class Solution {
public:
int InversePairs(vector<int> d) {
int mi = 0x7fffffff, mx = 0x80000000;
for(int i = 0; i < d.size(); ++i) mi = min(mi, d[i]), mx = max(mx, d[i]);
int r = 0;
BIT bit(mx - mi + 5);
for(int i = (int)d.size() - 1; i >= 0; --i){
r += bit.sum(d[i] - mi);
bit.add(d[i] - mi + 1, 1);
}
return r;
} };
//本来是个经典问题
//这么暴力都能通过。。。 数据规模竟然这么小。。。那这题目出来何用。。。
class Solution {
public:
int InversePairs(vector<int> d) {
int r = 0;
for(int i = 0; i < d.size(); ++i){
for(int j = 0; j < i; ++j) if(d[j] > d[i]) ++r;
}
return r;
}
};
编辑于 2016-07-23 03:49:09
回复(25)
class Solution {
public:
int InversePairs(vector<int> data) {
return mergeSort(data, 0, data.size() - 1);
}
private:
long long mergeSort(vector<int> &data, int s, int e) {
if (s >= e) return 0;
int mid = (e - s) / 2 + s;
long long num = mergeSort(data, s, mid) + mergeSort(data, mid + 1, e);
int i = s, j = mid + 1;
int cnt = 0;
vector<int> tmp;
while (i <= mid || j <= e) {
if (i > mid) {
tmp.push_back(data[j++]);
}
else if (j > e) {
num += cnt;
tmp.push_back(data[i++]);
}
else if (data[i] > data[j]) {
cnt++;
tmp.push_back(data[j++]);
}
else {
num += cnt;
tmp.push_back(data[i++]);
}
}
for (int i = s; i <= e; ++i) {
data[i] = tmp[i - s];
}
return num%1000000007;
}
};
发表于 2017-06-10 20:46:32
回复(0)
归并排序走一遍 合并时对于右边的数统计一下左边比他小的个数，此个数即为逆序对个数。
class Solution {
public:
void solve(int x, int y, vector<int> &A, vector<int> &B, int &ans){//B为临时空间
if(y - x > 1){
int mid = x + (y - x)/2, left = x, right = mid, i = x;
solve(x, mid, A, B, ans);
solve(mid, y, A, B, ans);
int zuo = mid - x;
while(left < mid || right < y){
if(right >= y || (left < mid && A[left] < A[right]))
{B[i++] = A[left++];zuo--;}
else {B[i++] = A[right++];ans = (ans+zuo)%1000000007;}
}
}
for(int i = x; i < y; i++) A[i] = B[i];
}
int InversePairs(vector<int> data) {
vector<int> tmp = data;
int ans = 0;
solve(0, data.size(), data, tmp, ans);
return ans;
}
};
发表于 2018-12-11 20:33:58
回复(1)
问题信息
难度：
779条回答
2709收藏
139159浏览
通过挑战的用户
查看代码-
2020-07-04 00:40:38 -
2020-07-04 00:32:27
-
2020-07-04 00:05:44 -
2020-07-03 23:28:13
-
2020-07-03 23:21:43
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客网公众号
- 公司地址：北京市朝阳区大屯路东金泉时代广场3单元北京牛客科技有限公司
- 联系方式：010-60728802(电话) admin@nowcoder.com
- 牛客科技© All rights reserved
- 京ICP备14055008号-4 增值电信业务经营许可证
-
京公网安备 11010502036488号
