lint0532. 逆序对

532. Reverse Pairs

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.

Example1
Input: A = [2, 4, 1, 3, 5]
Output: 3
Explanation:
(2, 1), (4, 1), (4, 3) are reverse pairs

Example2
Input: A = [1, 2, 3, 4]
Output: 0
Explanation:
No reverse pair

• 利用归并排序的思想求逆序对，复杂度O(nlog_n)当然也可以用树状数组或者线段树求解

public class Solution {
    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;
    }
}

另一个写法：

//解法二
public class Solution {
    /**
     * @param A an array
     * @return total of reverse pairs
     */
    private static  int[] aux;
    int num = 0;
    public long reversePairs(int[] A) {
        // Write your code here
         aux = new int[A.length];
        sort(A,0,A.length-1);
        return num;
    }

    private void sort(int[] a, int lo, int hi) 
    {
        if (hi<=lo) return;

        int mid = lo + (hi - lo)/2;
        //递归
        sort(a, lo, mid);//左半边排序
        sort(a, mid+1, hi);//右半边排序
        merge(a,lo,mid,hi);//归并结果
    }

    //归并算法
    private void merge(int[] a, int lo, int mid, int hi){
        int i = lo;
        int j = mid + 1;

        for(int k = lo; k <= hi; k++){
            aux[k] = a[k];
        }
        //每次k,i或j都会右移一个
        for (int k = lo; k <= hi; k++){
            if (i>mid) a[k] = aux[j++];//如果左边归并完，则只添加右边
            else if (j>hi) {

                a[k] = aux[i++];//如果右边归并完，则只添加左边
            }
            //如果右边的小于左边的，则添加右边的
            else if (aux[j] < aux[i]) {
                a[k] = aux[j++];
                //右边的小于左边的当前数，则他小于当前至mid的所有数，因为数组在合并时已经为有序的了。
                num+=mid-i+1;
                }
            else a[k] = aux[i++];//如果左边的小于右边的，则添加左边的
        }
    }
}

https://www.jiuzhang.com/solution/reverse-pairs