493. Reverse Pairs

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:

1. The length of the given array will not exceed 50,000.
2. All the numbers in the input array are in the range of 32-bit integer.

------------------------------
ref: https://leetcode.com/problems/reverse-pairs/solution/
BIT: https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/
关键是需要一个数据结构可以提供实时排序并计数。binary search tree可以满足，但是最坏情况是O(n^2)，得用AVL或Red-Black来实现。而BIT(binary indexed tree) 实现更简单

Solution #1 Binary Indexed Tree，遍历以[i] 为pair里第2位的所有pair，在[0, i - 1]内找所有符合 j < i && nums[j] >= 2 * num[i] + 1的个数并返回。根据算法要返回排序后的[j, i]数量，而普通的BIT实现是[0, i]和，所有这里要修改下read和update方法，使BIT存的是suffix sum。

想验证的该算法的话画一个[1, 8]的BIT就可以了

class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        int[] bit = new int[n + 1];
        int[] sorted = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sorted);
        
        int rt = 0;
        
        for (int i = 0; i < n; i++) {
            int index = getIndex(sorted, nums[i] * 2L + 1);
            rt += read(bit, index);
            int index2 = getIndex(sorted, nums[i]); 
            update(bit, index2);
        }
                        
        return rt;
    }
    
    private int getIndex(int[] sorted, long val) {
        int l = 0, r = sorted.length - 1;
        
        while (l <= r) {
            int m = (l + r) / 2;
            if (sorted[m] >= val) {
                r = m - 1;
            }else {
                l = m + 1;
            }
        }

        return l + 1;
    }
    
    private void update(int[] bit, int idx) {
        
        while (idx > 0) {
            bit[idx] += 1;
            idx -= idx & -idx;
        }
    }
    
    private int read(int[] bit, int idx) {
        int sum = 0;
        while (idx < bit.length) {
            sum += bit[idx];
            idx += idx & -idx;
        }
        
        return sum;
    }
}

Solution #2, 用merge sort的思路。分成2堆，pair里的第一个在第一堆，第二个在第二堆。这样能保证i < j， 然后再过滤 nums[i] > nums[j] * 2

class Solution {
    public int reversePairs(int[] nums) {
        return sort(nums, 0, nums.length - 1);
    }
    
    private int sort(int[] nums, int l, int r) {
        
        if (l >= r) {
            return 0;
        }
        
        int m = (l + r) / 2;
        int rt = sort(nums, l, m) + sort(nums, m + 1, r);
        
        int x = l, z = m + 1;
        while (x <= m && z <= r) {
            
            if (nums[x] > nums[z] * 2L) {
                rt += m - x + 1;            
                z++;
            }else {
                x++;    
            }
        }

        int i = l, j = m + 1;
        int[] backup = new int[r - l + 1];
        int p = 0;     
        
        while (i <= m || j <= r) {
            if (i > m || (j <= r && nums[i] >= nums[j])) {
                backup[p++] = nums[j++];
            }else {
                backup[p++] = nums[i++];
            }
        }
        
        for (int k = l; k <= r; k++) {
            nums[k] = backup[k - l];
        }
        
        return rt;
    }
}