剑指 Offer 51 数组中的逆序对

标签: 剑指 Offer 发布于:2022-02-27 10:34:43 编辑于:2022-02-27 15:42:26 浏览量:847

概述

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

这是一道 Hard 哦。

暴力遍历

显然可以 O(n^2) 暴力遍历。

但是不知道不同位置相同数字组成的逆序对是算一个还是多个?题目也没说清楚。

试了一下,是多个。

正好不用去重了。

果然 TLE:

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int count = 0;
        for (int i = 0; i < nums.size(); i ++) {
            for (int j = i + 1; j < nums.size(); j ++) {
                if (nums[i] > nums[j]) count ++;
            }
        }
        return count;
    }
};

基于归并排序的分治方法

对于数字 num[i],如果我们想要计算以其开头的逆序对,我们需要其之后后面小于 num[i] 的个数。

我们需要某种数据结构记录这一点。

可不可以利用已经计算过的值来协助我们做到这一点呢?

O(n^2) 的复杂度肯定是不行的,我们应该是需要先遍历一遍维护某种数据结构。


然而 no such thing,看了《剑指 Offer》上的解答,用的是分治。

有点麻烦,先写一道 Easy 题让我开心一下再回来写吧。


然而写完了并不开心,淦。


好叭,其实还好啦,不算麻烦。

归并的时候注意,我们需要检查是否有一个子数组已经完成归并:if (li <= m && ri <= r)

class Solution {
public:
    vector<int> temp;
    int reversePairs(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        temp = nums;
        return helper(nums, 0, nums.size() - 1);
    }

    int helper(vector<int>& nums, int l, int r) {
        if (l == r) return 0;
        if (l + 1 == r) {
            if (nums[l] > nums[r]) return 1;
            swap(nums[l], nums[r]);
            return 0;
        }
        int m = (l + r) / 2;
        int lc = helper(nums, l, m);
        int rc = helper(nums, m + 1, r);
        int cc = 0;
        int li = l;
        int ri = m + 1;
        for (int i = l; i <= r; i ++) {
            if (li <= m && ri <= r) {
                if (nums[li] > nums[ri]) {
                    cc += r - ri + 1;
                    temp[i] = nums[li ++];
                } else {
                    temp[i] = nums[ri ++];
                }
            } else {
                if (li <= m) {
                    temp[i] = nums[li ++];
                } else { // ri <= r
                    temp[i] = nums[ri ++];
                }
            }
        }
        for (int i = l; i <= r; i ++) {
            nums[i] = temp[i];
        }
        cout << lc << " " << rc << " " << cc << endl;
        return lc + rc + cc;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/