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

AcWing 65 数组中的逆序对

程序员文章站 2022-05-13 19:34:04
...

题目描述:

在数组中的两个数字如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。

输入一个数组,求出这个数组中的逆序对的总数。

样例

输入:[1,2,3,4,5,6,0]

输出:6

分析:

暴力做法,平方级复杂度,不予考虑。采用分治法优化,类似于归并排序的思路。假设merge函数可以返回一个区间内逆序对的个数,那么对于区间[l,r],我们划分为[l,mid]和[mid+1,r]两部分,最后逆序对的个数等于左边区间逆序对数目+右边区间逆序对数目+合并时逆序对的数目,比如456  123,合并时,左边4 > 1,由于归并排序时各个子区间必然是有序的,所以4是左边区间最小的数,4 > 1说明了4右边的所有数均大于1,一共mid - i + 1个数(i为指向4的指针),次数右指针右移到指向2,继续比较,以此类推。

class Solution {
public:
    int merge(vector<int> &nums,int l,int r){
        if(l >= r)  return 0;
        int mid = l + r >> 1;
        int res = merge(nums,l,mid) + merge(nums,mid + 1,r);
        int i = l,j = mid + 1;
        vector<int> temp;
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j])  temp.push_back(nums[i++]);
            else{
                temp.push_back(nums[j++]);
                res += mid - i + 1;
            }
        }
        while(i <= mid) temp.push_back(nums[i++]);
        while(j <= r)   temp.push_back(nums[j++]);
        i = l;
        for(auto x : temp)  nums[i++] = x;
        return res;
    }
    int inversePairs(vector<int>& nums) {
        return merge(nums,0,nums.size() - 1);
    }
};

 

相关标签: 分治法