[LeetCode]Reverse Pairs

这道题和之前的Count of Smaller Numbers after Self是一样的。同样有merge sort和BST两种解法，但是BST的解法没法过test case，是因为我们implement的并不是严格意义上的balanced binary search tree，最坏的情况可能到O(n^2)，所以我们用merge sort的解法来写，唯一不同的一点是对于i > j && 2 * nums[j] < nums[i]的才满足情况。我们在merge的时候也要做相应的调整，以half1 = {3,7,8}和half2 = {1,2,3}来举例，对于Count of Smaller Numbers after Self中的情况，也就是i > j && nums[j] < nums[i]，我们只需要在将half1中元素merge的时候统计half2已经被merge多少个元素(hi - (mid + 1))即可，这就是half1当前元素在这一轮当中找到的reverse pairs的数量。但是这道题的情况稍有不同，我们无法再用这种方法了，所以我们稍作改良，思路仍然一样，是运用双指针，假设p1,p2分别对应half1和half2的当前元素，我们在merge前先做一个预处理统计reverse pairs。我们移动p2直到其超过末尾或者nums[p2] * 2 >= nums[p1]，统计对于当前p1对应元素的reverse pairs，之后移动p1，重复以上步骤直到p1到达末尾，对于以上例子，步骤如下：

• p1指向3，p2指向2，reverse pairs = 1 {(3,1)}
• p1指向7，p2超出范围，reverse pairs = 1 + 3 {(7,1), (7,2), (7,3)}
• p1指向8，p2不变，reverse pairs = 4 + 3 {(8,1), (8,2), (8,3)}

这样的话我们可以在O(n)的时间完成统计和merge，时间复杂第O(n * log n)，代码如下：