Reverse Pairs 532

Question

For an array A, if i < j, and A [i] > A [j], called (A [i], A [j]) is a reverse pair. return total of reverse pairs in A.

Example

Given A = [2, 4, 1, 3, 5] , (2, 1), (4, 1), (4, 3) are reverse pairs. return 3

Solution

最容易想到的方法是依次查看每个元素和其后面所有元素是否是reverse pairs。但是该方法为O(n^2)，不够快。

O(nlogn)方法：利用mergetSort的性质，即将数组分为左右两个子数组，左边数组元素index都小于右边数组元素index，同时在merge的时候会挨个比较左右两个数组元素大小，此时只要左边数组某一个元素i大于右边数组某一个元素j，则从i开始到左边数组最后一个元素和j都是reverse pairs的关系。因此，每一次merge都能寻找reverse pairs。对于每一次切割，其reverse pairs为左边数组merge找到的reverse pairs的个数 ＋ 右边数组merge找到的reverse pairs的个数 ＋ 左右数组merge找到的reverse pairs的个数。

代码如下：

public class Solution {
    /**
     * @param A an array
     * @return total of reverse pairs
     */
    public long reversePairs(int[] A) {
        // Write your code here
        if(A == null || A.length == 0){
            return 0;
        }

        return mergeSort(A, 0, A.length - 1);
    }

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

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

        return sum;
    }

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

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

        while(left <= mid){
            temp[index++] = A[left++];
        }

        while(right <= end){
            temp[index++] = A[right++];
        }

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

        return sum;
    }
}