剑指 Offer 51. 数组中的逆序对【力扣】

2021/10/17 23:12:15

本文主要是介绍剑指 Offer 51. 数组中的逆序对【力扣】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题意理解

给定一个数组,计算逆序对的个数

问题分析

用归并

归并和逆序怎么关联?每次两个有序序列合并,对于左边的最小值放入最后序列的适合,最后序列左边的,比它小的,都是和逆序关系。问题转化为计算左边最小值放入最后序列时,右边序列已处理的元素个数。

其他

力扣

链接

class Solution {
public:
    int mergeSort(vector<int>& nums, vector<int>& tmps, int l, int h) {
        if (l >= h) return 0;
        int mid = (l + h) / 2;
        int vert = mergeSort(nums, tmps, l, mid) + mergeSort(nums, tmps, mid+1, h);
        int i = l, j = mid + 1, pos = l;
        while(i <= mid && j <= h) {
            if (nums[i] <= nums[j]) {
                tmps[pos] = nums[i];
                i++;
                vert += j - (mid+1);
            }
            else {
                tmps[pos] = nums[j];
                j++;
            }
            pos++;
        }
        while(i <= mid) {
            tmps[pos] = nums[i];
            pos++;
            i++;
            vert += j - (mid+1);
        }
        while(j <= h) {
            tmps[pos] = nums[j];
            pos++;
            j++;
        }
        copy(tmps.begin()+ l, tmps.begin() + h + 1, nums.begin() + l);
        return vert;
    }
    int reversePairs(vector<int>& nums) {
        int len = nums.size();
        vector<int> tmps(len);
        return mergeSort(nums, tmps, 0, len-1);    
    }
};



这篇关于剑指 Offer 51. 数组中的逆序对【力扣】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程