# 493.Reverse-Pairs

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/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

ๅฏๆ็ๆฏ๏ผๆไปฌ่ชๅฎไน็ๆ ๅนถไธๆฏไธไธชๅนณ่กกไบๅๆ ๏ผๅจๆๅ็ๆๅตไธไผๅฏผ่ด้ฟ้พ่กจ๏ผๅฆๆLeetCodeไธไฝฟ็จไธ่ฟฐไปฃ็ ไผๅฏผ่ดTLE(Time Limit Exceeded)ใ

``````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;
}
}
}``````

Last updated