# 493.Reverse-Pairs

## 493. Reverse Pairs

## 题目地址

<https://leetcode.com/problems/reverse-pairs/>

<https://lotabout.me/2018/binary-indexed-tree/>

## 题目描述

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

```java
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

```java
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)。

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/bit/493.reverse-pairs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.