数组中的逆序对
程序员文章站
2024-02-21 18:42:28
...
1、题目
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
2、解题
这是一个归并排序的
合并过程,主要是考虑合并两个有序序列时,计算逆序对数。
对于两个升序序列,设置两个下标:两个有序序列的末尾。每次比较两个末尾值,如果前末尾大于后末尾值,则有”后序列当前长度“个逆序对;否则不构成逆序对。然后把较大值拷贝到辅助数组的末尾,即最终要将两个有序序列合并到辅助数组并有序。
这样,每次在合并前,先递归地处理左半段、右半段,则左、右半段有序,且左右半段的逆序对数可得到,再计算左右半段合并时逆序对的个数。
class Solution {
public:
int InversePairs(vector<int> data) {
if(data.size()==0)return 0;
vector<int>copy;
for(int i = 0;i<data.size();i++){
copy.push_back(data[i]);
}
long long count = FindReserveCount(data,copy,0,data.size()-1);
return count%1000000007;
}
long long FindReserveCount(vector<int>&data,vector<int>©,int low,int high){
if(low>=high){
return 0;
}
int mid = (low+high)>>1;
long long leftCnt = FindReserveCount(data,copy,low,mid)%1000000007;
long long rightCnt = FindReserveCount(data,copy,mid+1,high)%1000000007;
int end1 = mid;
int end2 = high;
long long count = 0;
//申请辅助空间
int index = high;
while(end1>=low && end2>=mid+1){
if(data[end1]>data[end2]){
copy[index--] = data[end1--];
count += end2-mid;
}else{
copy[index--] = data[end2--];
}
}
while(end1>=low){
copy[index--] = data[end1--];
}
while(end2>=mid+1){
copy[index--] = data[end2--];
}
//写入原数组
for(int i = low;i<=high;i++){
data[i] = copy[i];
}
return leftCnt+rightCnt+count;
}
};