[LeetCode] 493. Reverse Pairs

[grandyang]

 

Given an array nums, we call (i, j) an  important reverse pair  if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2

 

Example2:

Input: [2,4,3,5,1]
Output: 3

 

Note:

1. The length of the given array will not exceed 50,000.
2. All the numbers in the input array are in the range of 32-bit integer.

 

这道题第一次做的时候就感觉和 Count of Smaller Numbers After Self 很像，开始也是用的二分查找法来建立有序数组，LintCode 上也有一道非常类似的题 Reverse Pairs 翻转对，虽然那道题没有加2倍的限制条件，但是思路都是一样的。于是我就开始稍稍改了一下，二分搜索的时候是搜索 nums[i]/2.0，加入数组的时候是加入原数 num，我记得当时是可以通过 OJ 的，但是后来 OJ 变的严格起来了，什么二分搜索啊，BST 啊之类的解法统统弄死，据目前来看，侥幸存活下来的方法就只有 BIT 和 MergeSort 这两种方法了。对于这类问题的本质的分析，大神 fun4LeetCode 的帖子讲的非常好，这里也借鉴一下大神的讲解来帮助理解吧。

对于这类数组找数字之间的关系的题，一种很好的解题思路就是拆分数组来解决子问题，就是把大问题拆成小问题，把小问题一一解决来，大问题的答案也就出来了，这么说起来是不是有点像 DP 的感觉，但是不同的是，博主感觉此类问题很难找到 DP 的状态转移方程吧。fun4LeetCode 大神归纳了两种拆分方法，一种叫顺序重现关系(Sequential Recurrence Relation)，用式子表示是 T(i, j) = T(i, j - 1) + C。这里的C就是处理最后一个数字的子问题，那么用文字来描述就是“已知翻转对的第二个数字为 nums[j], 在子数组 nums[i, j - 1] 中找翻转对的第一个数字”，这里翻转对的两个条件中的顺序条件已经满足，就只需要找比 2*nums[j] 大的数即可。当然最森破的方法就是线性扫描，但这样整个时间复杂度就会上升到令人发指的 O(n2)，这又怎么能逃过连 Binary Search 都不放过的 OJ 的魔爪。由于二分搜索和 BST 等方法已经被 OJ 阉割，所以我们只能用树状数组 Binary Indexed Tree 来做了。关于 BIT，我之前有篇博客 Range Sum Query - Mutable 应该讲的比较清楚了，如果弄懂了那篇博客，我们对 BIT 的机制也应该有个基本的了解，由于 BIT 的存储方式不是将数组中的数字对应的一一存入，而是有的对应存入，有的是存若干个数字之和，其设计初衷之一就是要在 O(lgn) 的时间复杂度下完成求和运算。那么我们该如何利用这一特性呢，这跟这道题又有什么关系呢，别着急，博主会慢慢解释。

首先我们应该确定一个遍历的方向，这里博主推荐从后往前遍历数组，这样做的好处是对于当前遍历到的数字，在已遍历过的数字中找小于当前数字的一半 (nums[i]/2.0) 的数字，这样的遍历方向也能跟上面的顺序重现关系的定义式统一起来。当然如果你想强行从前往后遍历，也不是不行，那么就需要在已遍历的数字中找大于当前数字的二倍 (nums[i]*2) 的数字就行了。由于我们要在之前遍历过的数字中找符合条件的数字，怎么样利用 BIT 的特性来快速的找到是这种解法的最大难点。我们需要将之前遍历过的数字存入 BIT 中，怎么存是难点。由于之前那篇博客我们知道 BIT 用 update 函数来存数，需要提供要存入的位置和要存入的数字这两个参数，那么这里难道我们就按照数字在原数组中的位置存入 BIT 吗，这样做毫无意义！我们要存的是该数字在有序数组中的位置，而且存入的也不是该数字本身，而是该数字出现的次数1。我们用题目中的第一个例子来说明，我们先给数组排序，得到：

1 1 2 3 3

对于每一个数字我们要确定其在 BIT 中的位置，由于有重复数字的存在，那么每个数字对应的位置就是其最后出现的位置，而且因为 BIT 是从1开始的，并不是像一般的数组那样从0开始，那么有如下对应关系：

1->2, 2->3, 3->5

那么当我们遇到数字1了，就 update(2,1)，遇到数字2了，就 update(3,1)，遇到数字3了，就 update(5,1)。我们之前解释了并不把数字本身存入 BIT，而是将其对应的位置存入 BIT，真正存入的数字是1，这样方便累加，而且由于1是固定的，在下面的代码中就不用将1当作函数的参数了。这样我们知道了如果存入数字，那么我们在遍历到新数字时，为了得到符合要求的数字的个数，需利用 BIT 的 getSum 函数。getSum 函数需要提供一个位置参数，可以返回该位置之前的所有数之和。同理，我们提供的参数既不是当前遍历到的数字本身，也不是其在原数组中的位置，而是该数字的一半 (nums[i]/2.0) 在有序数组中的正确位置，可以用 lower_bound 函数来找第一个不小于目标值的位置，当然我们也可以自己写个二分搜索的子函数来代替 lower_bound 函数。比如我们当前遍历到的数字是3，那么我们在有序数组中找 1.5 的位置，返回是2，此时我们在 BIT 中用 getSum 来返回位置2之前的数字之和，返回几就表示有几个小于 1.5 的数字。讲到这里基本上这种解法的核心内容都讲完了，如果你还是一头雾水，那么就是博主的表述能力的问题了(沮丧脸:()。那么博主只能建议你带实例一步一步去试，看看每一步操作后 BIT 中的结果是啥，下面就列出这些内容：

update(2,1) -> BIT: 0 0 1 0 1 0

update(5,1) -> BIT: 0 0 1 0 1 1

update(3,1) -> BIT: 0 0 1 1 2 1

update(5,1) -> BIT: 0 0 1 1 2 2

update(2,1) -> BIT: 0 0 2 1 3 2

 

解法一：

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int res = 0, n = nums.size();
        vector<int> v = nums, bit(n + 1);
        sort(v.begin(), v.end());
        unordered_map<int, int> m;
        for (int i = 0; i < n; ++i) m[v[i]] = i + 1;
        for (int i = n - 1; i >= 0; --i) {
            res += getSum(lower_bound(v.begin(), v.end(), nums[i] / 2.0) - v.begin(), bit);
            update(m[nums[i]], bit);
        }
        return res;
    }
    int getSum(int i, vector<int>& bit) {
        int sum = 0;
        while (i > 0) {
            sum += bit[i];
            i -= (i & -i);
        }
        return sum;
    }
    void update(int i, vector<int>& bit) {
        while (i < bit.size()) {
            bit[i] += 1;
            i += (i & -i);
        }
    }
};

 

fun4LeetCode 大神归纳的第二种方法叫做分割重现关系 (Partition Recurrence Relation)，用式子表示是 T(i, j) = T(i, m) + T(m+1, j) + C。这里的C就是处理合并两个部分的子问题，那么用文字来描述就是“已知翻转对的两个数字分别在子数组 nums[i, m] 和 nums[m+1, j] 之中，求满足要求的翻转对的个数”，这里翻转对的两个条件中的顺序条件已经满足，就只需要找到满足大小关系的的数对即可。这里两个数字都是不确定的，如果用暴力搜索肯定会被 OJ 唾弃。但是如果两个子数组是有序的，那么我们可以用双指针的方法在线性时间内就可以统计出符合题意的翻转对的个数。要想办法产生有序的子数组，那么这就和 MergeSort 的核心思想完美匹配了。我们知道混合排序就是不断的将数组对半拆分成子数组，拆到最小的数组后开始排序，然后一层一层的返回，最后原数组也是有序的了。这里我们在混合排序的递归函数中，对有序的两个子数组进行统计翻转对的个数，区间 [left, mid] 和 [mid+1, right] 内的翻转对儿个数就被分别统计出来了，此时还要统计翻转对儿的两个数字分别在两个区间中的情况，那么i遍历 [left, mid] 区间所有的数字，j则从 mid+1 开始检测，假如 nums[i] 大于 nums[j] 的二倍，则这两个数字就是翻转对，此时j再自增1，直到不满足这个条件停止，则j增加的个数就是符合题意的翻转对的个数，所以用当前的j减去其初始值 mid+1 即为所求，然后再逐层返回，这就完美的实现了上述的分割重现关系的思想。整个的写法非常的简洁，实在是太叼了。博主的直觉表明，fun4LeetCode 大神肯定是国人，不要问我为什么，因为这么强的肯定是中国人，哈～

 

解法二：

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0, nums.size() - 1);
    }
    int mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return 0;
        int mid = left + (right - left) / 2;
        int res = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);
        for (int i = left, j = mid + 1; i <= mid; ++i) {
            while (j <= right && nums[i] / 2.0 > nums[j]) ++j;
            res += j - (mid + 1);
        }
        sort(nums.begin() + left, nums.begin() + right + 1);
        return res;
    }
};

 

Github 同步地址：

#493

 

类似题目：

Count of Range Sum

Count of Smaller Numbers After Self

 

参考资料：

https://leetcode.com/problems/reverse-pairs/

https://leetcode.com/problems/reverse-pairs/discuss/97287/C%2B%2B-with-iterators

https://leetcode.com/problems/reverse-pairs/discuss/97280/very-short-and-clear-mergesort-bst-java-solutions

https://leetcode.com/problems/reverse-pairs/discuss/97268/general-principles-behind-problems-similar-to-reverse-pairs

https://leetcode.com/problems/reverse-pairs/discuss/97311/evolve-from-brute-force-to-optimal-a-review-of-all-solutions

 

LeetCode All in One 题目讲解汇总(持续更新中...)

[lld2006]

解法1很神， 谈谈感想
0， 如果对BIT不明白， 请去topcoder看bit index tree的教程

1 , “2.0”， 自己写的code死活不过，最后研究了大半天才发现是这个非常传神的2.0引起的； 如果想用整形， 那么对于非负数， 第一个大于等于 nums[i]的一半的数是（nums[i]+1)/2； 而对于负数则是 nums[i]/2， 非常容易忽略！

2, 为什么要sort这个数组？ 因为BIT处理的数是从1-->nmax，负数是不能处理的， 我们必需做映射， n1<n2<n3 ---> 1，2，3， 做成这样一个映射后bit需要handle的最大的数值就是nums.size(), 这样极大的提高了bit查找的效率， 并减少了对空间的消耗， 设想如果有一个数是2e9，那我们直接用bit内存消耗就太大了，查找和更新的效率也非常低， 更甚者， 负数是没法处理的

3, lower_bound 因为我们在bit中需要的是所有小于nums[i]/2的数对应的index， 那么下一个就是大于等于nums[i]/2.0的数， 这个是可以用lower_bound函数找到的；所以直接找这个大于等于的数在nums里的index就好了；unordered_map 用排好序的最后一个index，恰好利用bit这个天然的offset 1， 这个非常传神的体现在了调用getsum这个函数那一行！！！

4， 没有处理过这样的问题经验， 现场写出来正确的程序可能性是0， 坑太多了