剑指 Offer 51 数组中的逆序对

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

概述

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;
    }
};

Links: sword-offer-51