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.

Tips:

BIT: 和count of smaller number after itself 类似， 就是这次因为要大于两倍，所以取BIT中的index用二分搜索搜一下。这次从原数列的头开始，找到比当前数的两倍还要大的第一个数，取出他之后的所有数（因为都满足要求）并更新数组，更新数组时是更新比当前数小的所有数。

Merge Sort: 分两组，左右各自有序，如果右边的小于左边/2，就加上右边到最后所有的数。

In each round, we divide our array into two parts and sort them. So after "int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e); ", the left part and the right part are sorted and now our only job is to count how many pairs of number (leftPart[i], rightPart[j]) satisfies leftPart[i] <= 2*rightPart[j].

For example, left: 4 6 8 right: 1 2 3 so we use two pointers to travel left and right parts. For each leftPart[i], if j<=e && nums[i]/2.0 > nums[j], we just continue to move j to the end, to increase rightPart[j], until it is valid. Like in our example, left's 4 can match 1 and 2; left's 6 can match 1, 2, 3, and left's 8 can match 1, 2, 3. So in this particular round, there are 8 pairs found, so we increases our total by 8.

Code:

BIT:

public class Solution {
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] copy = Arrays.copyOf(nums, nums.length);
        int[] tree = new int[nums.length + 1];
        Arrays.sort(copy);
        int res = 0;
        for (int num : nums) {
            res += get(index(copy, 2L * num + 1), tree);
            update(index(copy, num), tree);
        }
        return res;
    }
    private int get(int i, int[] tree) {
        int res = 0;
        while (i < tree.length) {
            res += tree[i];
            i += i & (-i);
        }
        return res;
    }
    private void update(int i, int[] tree) {
        while (i > 0) {
            tree[i]++;
            i -= i & (-i); 
        }
    }
    private int index(int[] copy, long val) {
        int l = 0, r = copy.length - 1, m = 0;
        while (l <= r) {
            m = l + (r - l) / 2;
            if (copy[m] >= val) r = m - 1;
            else l = m + 1;
        }
        return l + 1;
    }
}

Merge Sort:

public class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length-1);
    }
    private int mergeSort(int[] nums, int s, int e){
        if(s>=e) return 0; 
        int mid = s + (e-s)/2; 
        int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e); 
        for(int i = s, j = mid+1; i<=mid; i++){
            while(j<=e && nums[i]/2.0 > nums[j]) j++; 
            cnt += j-(mid+1); 
        }
        Arrays.sort(nums, s, e+1); 
        return cnt; 
    }
}

九章：

public class Solution {
    /**
     * @param A an array
     * @return total of reverse pairs
     */
    public long reversePairs(int[] A) {
        return mergeSort(A, 0, A.length - 1);
    }

    private int mergeSort(int[] A, int start, int end) {
        if (start >= end) {
            return 0;
        }

        int mid = (start + end) / 2;
        int sum = 0;
        sum += mergeSort(A, start, mid);
        sum += mergeSort(A, mid+1, end);
        sum += merge(A, start, mid, end);
        return sum;
    }

    private int merge(int[] A, int start, int mid, int end) {
        int[] temp = new int[A.length];
        int leftIndex = start;
        int rightIndex = mid + 1;
        int index = start;
        int sum = 0;

        while (leftIndex <= mid && rightIndex <= end) {
            if (A[leftIndex] <= A[rightIndex]) {
                temp[index++] = A[leftIndex++];
            } else {
                temp[index++] = A[rightIndex++];
                sum += mid - leftIndex + 1;
            }
        }
        while (leftIndex <= mid) {
            temp[index++] = A[leftIndex++];
        }
        while (rightIndex <= end) {
            temp[index++] = A[rightIndex++];
        }

        for (int i = start; i <= end; i++) {
            A[i] = temp[i];
        }

        return sum;
    }
}