Reverse Pairs （第二周：分治法）

问题描述

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.

Example:

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

Output: 2

Example:

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

Output: 3

算法思路

主要是使用了分治的思想： 1. 其实就是传统的逆序数问题，基于归并排序算法来做即可，只不过稍微复杂了点，该题还要使用到二分查找。 2. 对于一个序列a，其长度为n，我们将其分为左右两部分，分别是序列b与序列c。a的逆序数又3分别组成：b的逆序数数目+c的逆序数数目+b中的数大于c中的数的2倍的数对。 3. 前两个结果我们可以根据分治得到，关键在于第三个。我每次得到b与c序列后，对其进行归并排序，对于第二个序列，即序列c中的每一个元素cj$c_j$，在归并的时候，在b中查找到最小的大于cj$c_j$的元素bi$b_i$的位置pos，既然在b中，大于2倍cj$c_j$的数有n2−pos$/frac{n}{2} - pos$个。 4. 至于如何查到pos，如果用线性搜索，则会超时，我们使用了二分查找。与传统二分搜索不同的是，我们不是要找目标值的位置，当查找值等于目标值的时候，下界要加一。 5. 要注意的是，样例使用的数字比较大，在进行数字判断的时候，要把数字从int类型转成double类型或者long类型。

算法代码