【LeetCode】剑指 Offer（26）

2023-04-22

int 数组 nums

目录题目：剑指Offer51.数组中的逆序对-力扣（Leetcode）题目的接口：解题思路：代码：过啦！！！写在最后：题目：剑指Offer51.数组中的逆序对-力扣（Leetcode）题目的接口：classSolution{public:intreversePairs(vector<int&g

题目：剑指 Offer 51. 数组中的逆序对 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

题目：剑指 Offer 51. 数组中的逆序对 - 力扣（Leetcode）

题目的接口：


class Solution {
public:
    int reversePairs(vector<int>& nums) {
 
    }
};

解题思路：

这一道题，我的思路是用双指针暴力求解，

但这个数组长度，O(N^2)的时间复杂度肯定是不可能把所有样例跑完，

看了大佬的思路，用的是归并排序，（如果不会归并排序，最好先去学一下）

我一开始看了很久没有搞明白为什么，

实际上，这个思路是利用的归并排序的一个特性，具体思路如下：

例：数组 [ 7, 5, 2, 6, 0, 1, 5, 4 ]

我们就拿这个数组归并到最后一步的时候作为样例：

[ 2, 5, 6, 7 ] 和 [ 0, 1, 4, 5 ]

由于他们通过先前的归并已经是两个有序的数组，

而最后一步就两个数组每个元素比大小，然后尾插到临时数组上，最后再拷贝回来，

重点来了：

第一个数比大小 2 > 0 所以尾插 0 并让第二个数组的下标begin2++，

因为这两个是升序数组，2 > 0，也表明 2 之后的所有数都大于 0 ,

那么这里就有 4 ( mid + 1，也就是第一个数组的长度) 个逆序数对，

那么，当 2 和 4 比较，2 < 4 ，就尾插 2 进临时数组，让第一个数组下标begin1++，

这个时候，继续往下比较，5 > 4，尾插 4 并让第二个数组的下标begin2++，

因为这两个是升序数组，5 > 4，也表明 5 之后的所有数都大于 4，

但是因为第一个数组已经是第二个数了，所以：

这里就有 3 （ mid + 1 - begin1 （也就是减去第一个数组的下标））个逆序数对。

综上所述，

我们只需要在第一个数组的值 > 第二个数组的值的时候，记录逆序数对 (mid + 1 - begin1) 即可。

下面是代码：

代码：


class Solution {
public:
    //计数
    int res = 0;
    int reversePairs(vector<int>& nums) {
        //创建临时数组
        vector<int> tmp(nums.size());
        //归并排序，我用的是我学的归并排序模板
        merge_sort(nums, tmp, 0, nums.size() - 1);
        return res;
    }
private:
    void merge_sort(vector<int>& nums, vector<int>& tmp, int begin, int end) {
        if(begin >= end) return; //返回
 
        //分治
        int mid = (begin + end) >> 1;
        merge_sort(nums, tmp, begin, mid);
        merge_sort(nums, tmp, mid + 1, end);
        //[begin][mid], [mid + 1][end]
 
        //两个数组的下标
        int begin1 = begin, end1 = mid;
        int begin2 = mid + 1, end2 = end;
 
        //临时数组的下标
        int i = begin;
 
        //比较大小之后尾插进临时数组
        while(begin1 <= end1 && begin2 <= end2) {
            if(nums[begin1] <= nums[begin2]) {
                tmp[i++] = nums[begin1++];
            }
            else {
                tmp[i++] = nums[begin2++];
                //计算这一段的逆序数对数量//具体推导看文章的文字
                res += mid + 1 - begin1; //整个思路的核心
            }
        }
 
        //将没有插完的值全部尾插进临时数组
        while(begin1 <= end1) tmp[i++] = nums[begin1++];
        while(begin2 <= end2) tmp[i++] = nums[begin2++];
 
        //将临时数组拷贝回原数组
        for(int i = begin; i <= end; i++) {
            nums[i] = tmp[i];
        }
    }
};