Comment on page

# 493.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.
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.

## 代码

### Approach #1 Merge Sort

class Solution {
public int reversePairs(int[] nums) {
int n = nums.length;
if (nums == null || n == 0) return 0;
return mergeSort(nums, 0, n - 1);
}
private int mergeSort(int[] nums, int start, int end) {
if (start >= end) return 0;
int mid = start + (end - start) / 2;
int res = mergeSort(nums, start, mid) + mergeSort(nums, mid+1, end);
int j = mid + 1;
for (int i = start; i <= mid; i++) {
while (j <= end && nums[i] / 2.0 > nums[j]) { // 防止溢出
j++;
}
res += j - (mid + 1);
}
Arrays.sort(nums, start, end + 1);
return res;
}
}

### Approach #2 BIT

class Solution {
public int reversePairs(int[] nums) {
int[] nums_copy = Arrays.copyOf(nums, nums.length);
Arrays.sort(nums_copy);
int[] bit = new int[nums_copy.length + 1];
int cnt = 0;
for (int num: nums) {
// 利用BIT数据结构统计大于2*num的元素个数
cnt += query(bit, index(nums_copy, num * 2L + 1));
// 插入当前元素，这里index是num在copy中的下标
insert(bit, index(nums_copy, num));
}
return cnt;
}
// 返回大于或者等于target的坐标，如果多个target返回第一个坐标
private int index(int[] nums, long target) {
int start = 0;
int end = nums.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] >= target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
// bit数组是以1为开始，所以返回start+1
return start + 1;
}
private void insert(int[] bit, int i) {
while (i > 0) {
bit[i] ++; // 比bit[i]大的个数
i -= i & -i;
}
}
private int query(int[] bit, int i) {
int sum = 0;
while (i < bit.length) {
sum += bit[i];
i += i & -i;
}
return sum;
}
}

### Approach #3 BST

public class Solution {
public int reversePairs(int[] nums) {
Node root = null;
int[] cnt = new int[1];
for (int i = nums.length-1; i>=0; i--) {
search(cnt, root, nums[i]/2.0);//search and count the partially built tree
root = build(nums[i], root);//add nums[i] to BST
}
return cnt[0];
}
private void search(int[] cnt, Node node, double target){
if (node == null) return;
else if(target == node.val) cnt[0] += node.less;
else if(target < node.val) search(cnt, node.left, target);
else {
cnt[0] += node.less + node.same;
search(cnt, node.right, target);
}
}
private Node build(int val, Node n) {
if (n == null) return new Node(val);
else if (val == n.val) n.same+=1;
else if (val > n.val) n.right = build(val, n.right);
else {
n.less += 1;
n.left = build(val, n.left);
}
return n;
}
class Node{
int val, less = 0, same = 1;//less: number of nodes that less than this node.val
Node left, right;
public Node(int v){
this.val = v;
}
}
}