在數(shù)組中的兩個數(shù)字如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)?。給你一個數(shù)組，求出這個數(shù)組中逆序?qū)Φ目倲?shù)。
概括：如果a[i] > a[j] 且 i < j， a[i] 和 a[j] 構(gòu)成一個逆序?qū)Α?/p>

這道題方法有兩種，第一種暴力法，第二種使用歸并排序來計算逆序?qū)Α?/p>

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

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;
    }
}

所以我覺得這道題，應(yīng)該還有解法，所以在博客上有人說，利用歸并排序，可以求出逆序?qū)ΑＰ适且哂谖覀兊谋┝Ψǖ?。代碼如下：

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;
        // 把較小的數(shù)先移到新數(shù)組中
        while (i <= mid && j <= high) {
            if (num[i]<=num[j]) {
                temp[k++] = num[i++];
                
            } else {
                temp[k++] = num[j++];
                result+=(mid-i+1);
            }
        }
        // 把左邊剩余的數(shù)移入數(shù)組
        while (i <= mid) {
            temp[k++] = num[i++];
        }

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

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

結(jié)果：

image.png