在數組中的兩個數字如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。給你一個數組，求出這個數組中逆序對的總數。
概括：如果a[i] > a[j] 且 i < j， a[i] 和 a[j] 構成一個逆序對。

這道題方法有兩種，第一種暴力法，第二種使用歸并排序來計算逆序對。

第一個暴力法，相信我們很容易想到，代碼也不多。但我在lintcode提交了4次，有一次出現了時間超時。

QQ截圖20170610192512.png

public class Solution {
    /**
     * @param A an array
     * @return total of reverse pairs
     */
    public long reversePairs(int[] A) {
      long result = 0;
        for (int i = 0; i < A.length-1; i++) {
            for (int j = i + 1; j < A.length; j++) {
                if (A[i] > A[j]) {
                    result++;
                }
            }
        }
        return result;
    }
}

所以我覺得這道題，應該還有解法，所以在博客上有人說，利用歸并排序，可以求出逆序對。效率是要高于我們的暴力法的。代碼如下：

public class Solution {
    /**
     * @param A an array
     * @return total of reverse pairs
     */
    private long result;
    public long reversePairs(int[] A) {
     sort(A, 0, A.length - 1);
        return result;
    }
    private void sort(int[] num, int low, int high) {
        int mid = (high + low) / 2;
        if (low < high) {
            // 左邊排序
            sort(num, low, mid);
            // 右邊排序
            sort(num, mid + 1, high);
            // 左右合并
            mergeSort(num, low, mid, high);
        }
    }

    private void mergeSort(int[] num, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左指針
        int j = mid + 1;// 右指針
        int k = 0;
        // 把較小的數先移到新數組中
        while (i <= mid && j <= high) {
            if (num[i]<=num[j]) {
                temp[k++] = num[i++];
                
            } else {
                temp[k++] = num[j++];
                result+=(mid-i+1);
            }
        }
        // 把左邊剩余的數移入數組
        while (i <= mid) {
            temp[k++] = num[i++];
        }

        // 把右邊邊剩余的數移入數組
        while (j <= high) {
            temp[k++] = num[j++];
        }

        // 把新數組中的數覆蓋nums數組
        for (int k2 = 0; k2 < temp.length; k2++) {
            num[k2 + low] = temp[k2];
        }
    }
}

結果：

image.png