ReversePairs原题
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:
The length of the given array will not exceed 50,000.
All the numbers in the input array are in the range of 32-bit integer.
ReversePairs是LeetCode Weekly Contest 19的最后一题，很可惜没有做出来。这篇文章就是针对此类数组问题做出的总结。
解决复杂的数组类问题主要思想就是动态规划：将数组拆分，解决子问题。
问题定义
假设一个数组nums，含有n个元素。nums[i, j]表示下标从i到j的子数组。T(i, j)表示当前问题在子数组nums[i, j]下的解，例如在ReversePairs中，T(i, j)表示子数组nums[i, j]中所有反转元素对的个数。
有了上面的定义，原始问题的解自然而然就是T(0, n-1)。现在我们主要的问题是，如何找到从子问题解中得到原问题的解，动态规划中叫做状态转移方程。找到子问题的解，并且找到原问题与子问题的联系，自然而然可以得到原问题的解。至此，我们描述的都是动态规划的常规解题过程。
当谈，在数组这个框架下面有很多中寻找T(i, j)的递推关系的方法，这里我们介绍最常用的两种：
- T(i, j) = T(i, j-1) +C, 顺序处理，C表示处理最后一个元素的子问题，这种方式叫做顺序递推关系。
- T(i, j) = T(i, m) + T(m + 1, j) + C，其中m=(i+j)/2，子数组nums[i, j]会被进一步划分为两个部分，C表示联系这两个部分的子问题，这种方式叫做分区递推关系。
这两种情况下面，子问题C如何表述，依赖我们原始的问题，并决定了原始问题的时间复杂度。所以找到一种高效算法去解决子问题是至关重要的。
下面我们把这两种递推方式用于解决"Reverse Pairs"。
顺序递推关系的解法
假设输入数组为nums中有n个元素，T(i, j)表示nums[i, j]的所有“逆序对”，我们设置i为0，也就是说子数组永远从开头开始。因此我们得到：
T(0, j) = T(0, j-1) + C
子问题C变成“找到这样的逆序对，第一个元素来自于nums[0, j-1]，第二个元素为nums[j]”
所谓的“逆序对”(p, q)必须满足以下几个条件：
- p<q: 第一个元素的下标必须小于第二个元素。
- nums[p] > 2 * nums[q]：第一个元素必须大雨第二个元素的两倍。
对于子问题C，第一个条件是自然而然就满足的，我们的问题即求出满足第二个条件的nums[0, j-1]中所有大于nums[j]*2的元素。
最简单的方法是直接顺序扫描nums数组，对于该问题来说一次扫描的代价是O(n)，解决该问题的复杂度是O(n^2)。
为了提高查找的效率，一个关键点在于子数组的元素顺序并不影响最后的结果，因此可以先排序，后做二分查找。我们用BST可以实现这个过程。
ReversePairs问题的BST解法
//自定义Node
public class ReverseNode{
public int val;
public int cnt;
ReverseNode left;
ReverseNode right;
public ReverseNode(int val){
this.val = val;
this.cnt = 1;
}
}
//定义插入和查询
private int search(ReverseNode root, long val){
if(root==null)
return 0;
if(val==root.val)
return root.cnt;
if(val < root.val)
return root.cnt+search(root.left, val);
return search(root.right, val);
}
private ReverseNode insert(ReverseNode root, int val){
if(root==null)
return new ReverseNode(val);
if(val==root.val){
root.cnt++;
return root;
}else if(val>root.val) {
//这里有个小技巧，插入值比当前值大的时候当前节点计数增加，这样当前节点下面右子树的节点个数就可以确定，即比查找值大的所有节点个数
root.cnt++;
return insert(root.right, val);
}else
return insert(root.left, val);
}
public int reversePairs(int[] nums) {
int res = 0;
ReverseNode root = null;
for (int ele : nums) {
res += search(root, 2L * ele + 1);
root = insert(root, ele);
}
return res;
}
可惜的是，我们自定义的树并不是一个平衡二叉树，在最坏的情况下会导致长链表，如果LeetCode上使用上述代码会导致TLE(Time Limit Exceeded)。
ReversePairs问题的BIT解法
BIT数据结构可以参考我的另一篇文章BIT数据结构。
BIT解法的思想和BST相同，都是从已有的数据中寻找符合nums[p] > 2 * nums[q]的个数，找到之后累计到结果上并将当前值插入到BIT结构中，完成一个循环，但是BIT方法的时间复杂度是确定的，为O(n*logn)。
在之前的文章中，BIT数据结构用来保存数组元素的部分和，并且将求部分和操作的时间复杂度降低到O(logn)，这里利用的是BIT这个特性。
首先定义BIT插入和搜索操作，这里的插入和搜索参数i为需要插入和搜索的数字在有序数组中的下标：
//i为有序数组的下标
private int search(int[] bit, int i) {
int sum = 0;
while (i < bit.length) {
sum += bit[i];
i += i & -i;
}
return sum;
}
//i为有序数组的下标
private void insert(int[] bit, int i) {
while (i > 0) {
bit[i] += 1;
i -= i & -i;
}
}
主函数如下：
public int reversePairs(int[] nums) {
int res = 0;
int[] copy = Arrays.copyOf(nums,nums.length);
int[] bit = new int[copy.length+1];
//对拷贝数组排序，为了得到大小排序过的位置。
Arrays.sort(copy);
for (int ele : nums) {
//利用bit数据结构统计大于2*ele的元素个数
res += search(bit, index(copy,2L * ele + 1));
//插入当前元素，这里如餐是ele在copy中的下标
insert(bit, index(copy,ele));
}
return res;
}
//返回大于或者等于val的坐标，如果多个val返回第一个坐标
private int index(int[] nums, long val){
int l = 0, r = nums.length - 1, m = 0;
while (l <= r) {
m = l + ((r - l) >> 1);
if (nums[m] >= val) {
r = m - 1;
} else {
l = m + 1;
}
}
//bit数组是以1为开始，所以返回l+1
return l + 1;
}
分区递推关系的解法
分区递推关系，设置
i=0, j=n-1, m=(n-1)/2
T(0, n-1)=T(0,m) + T(m+1, n-1) +C
子问题C代表的的是：找到符合题意得元素对，第一个元素来自于左子数组num[0,m]中，同时第二个元素来自于右子数组nums[m+1, n-1]。解决该子问题，我们就可以解决问题。
一个最容易想到的方法是扫描两个子数组得到子问题的解，复杂度是O(n^2)。
子问题中，两个子数组中的元素顺序并不影响子问题的解决。对子数组做排序，反转对的个数可以在线性时间里面找到。两个索引同时对左右子数组做扫描，一次扫描可以得到结果。
下面的问题是，如何对子数组做排序。最好的一个方案是merge排序算法（组合排序），在做merge的时候子数组已经排序，可以直接做搜索。以下是上述思想的代码实现。
public int reversePairs(int[] nums) {
return reversePairs(nums, 0, nums.length-1, 2);
}
private int reversePairs(int[] nums, int start ,int end, int L){
if(start>=end)
return 0;
int mid = start+((end-start)>>1);
int res = reversePairs(nums, start, mid, L )+reversePairs(nums, mid+1, end, L);
int i=start;
int j = mid+1;
int k=0;
int reR = mid+1;
int[] tempArray = new int[end-start+1];
while(i<=mid){
while(reR<=end&&nums[i]>nums[reR]*(long)L) reR++;
res+=reR-(mid+1);
while(j<=end&&nums[i]>nums[j]) tempArray[k++] =nums[j++];
tempArray[k++] = nums[i++];
}
while(j<=end){
tempArray[k++] = nums[j++];
}
System.arraycopy(tempArray,0,nums,start,end-start+1);
return res;
}
public static void main(String[] args) {
int[] nums =new int[]{1,3,2,3,1};
NO493_ReversePairs_Merge merge = new NO493_ReversePairs_Merge();
System.out.println(merge.reversePairs(nums));
}
总结
很多涉及到数组的问题可以找到对应的子问题，当我们找到子问题的解和子问题与原问题的联系，那么原问题自然而然就解决了。一般划分子问题有两种方法，一种是线性递推方法，一种是分区递推方法。
如果子问题C涉及到动态的搜索空间，可以考虑搜索和插入较快的数据结构例如:自平衡二叉树，二叉搜索树，线段树等等。
如果分区递推法的子问题C涉及到排序，那么归并排序是一个很好的排序算法，在排序的同时可以将搜索算法嵌入其中。这样代码会更加优雅。如果子问题之间存在重合，那么可以将中间结果缓存，防止重复计算（这也是动态规划常用的方法）。
参考
https://leetcode.com/problems/reverse-pairs/discuss/97268/General-principles-behind-problems-similar-to-%22Reverse-Pairs%22
https://www.jianshu.com/p/e713c1f7d0cd
