逆序对（lintcode第532题难度中等）

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。给你一个数组，求出这个数组中逆序对的总数。
概括：如果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