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

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