在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围: 对于
对于
数组中所有数字的值满足 
要求:空间复杂度
,时间复杂度
题目保证输入的数组中没有的相同的数字
[1,2,3,4,5,6,7,0]
7
[1,2,3]
0
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; } };
/*归并排序的改进,把数据分成前后两个数组(递归分到每个数组仅有一个数据项), 合并数组,合并时,出现前面的数组值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; } }
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挺蛋疼的。
public class Solution { int cnt, CONST = 1000000007; public int InversePairs(int[] array) { int[] B = new int[array.length]; sort(array, B, 0, array.length - 1); return cnt; } void sort(int[] A, int[] B, int l, int r) { if (l >= r) return; int m = (l + r) >> 1; sort(A, B, l, m); sort(A, B, m + 1, r); merge(A, B, l, m, r); } void merge(int[] A, int[] B, int l, int m, int r) { int i = l, j = m + 1, t = l; for (; i <= m && j <= r; ) if (A[i] > A[j]) { cnt = (cnt + (m - i + 1) % CONST) % CONST; //key code B[t++] = A[j++]; } else B[t++] = A[i++]; for (; i <= m; ) B[t++] = A[i++]; for (; j <= r; ) B[t++] = A[j++]; for (i = l; i <= r; i++) A[i] = B[i]; } }
这个之前的笔记中已经说过这道题目了,是归并排序的典型应用。归并排序的基本思想是分治,在治的过程中有前后数字的大小对比,此时就是统计逆序对的最佳时机。
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];
}
}
//大家好,我是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; } };
略微修改了书上的思路,直接归并将序排列,这样可以从头开始比较。其余思路一样 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++]; } };
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); }
# -*- 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 #我惊呆了,就是通不过,这没多复杂吧我的哥
代码参考剑指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; } };
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; } };
//这道题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; } } } };
/* *归并排序的思想,最后求得的逆序数进行取摸 % 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; } }
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
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
//运行时间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]; }
#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; } };
#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; } };
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; } };
归并排序走一遍 合并时对于右边的数统计一下左边比他小的个数,此个数即为逆序对个数。
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;
}
};