欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数组中的逆序对

程序员文章站 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>&copy,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;
    }
};
相关标签: 牛客练习