剑指offer面试

题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组的逆序对的总数。

思路

最初见到题目想到的思路应该不会太难：对于遍历到的每一个数字，都以此数字作为起点，与后面的数字作为比较，如果大于后面的数字，则逆序数加一。

于是这种算法的时间复杂度为：O(N^2)。

有没有更小的时间复杂度呢？

当时想到了以空间换取时间的思路，但是没有想到具体的实现方法的思路。看了剑指offer上面的提示，才知道：原来用一种排序方法可以做到：归并排序。

该排序有O(NlogN)的时间复杂度，但是由于在其中用到辅助数组，故空间复杂度为O(N).

关于归并排序的详细思路请参见：https://github.com/leexuehan/leexuehan.github.com/issues/4。

此处只说怎么把统计逆序数加进去。

就举一个简单的例子：数组 [9，5，2，7].

因为归并是一个不断分割再排序的过程，所以大致过程如下：

9    |    5    |    2    |    7
    5    9    |    2    7
    2    5    7    9

接下来需要将 2 与 5 和 9 相比较。

因为往辅助数组拷贝的时候，首先拷贝到其中的数字是 2，然后因为5 是第一组里面最小的数字，如果 2 比 5 还小的话，说明比后面的都小，所以此时逆序数的值就要加上 第一组的长度，在代码中就是 mid - i -1.

剩下的依次类推。

代码

package com.ans;

public class Solution4 {

private static int retVal = 0;
public static int merge(int start, int end, int[] arr, int[] tmp) {
    if (start >= end)
        return -1;
    int mid = (start + end) / 2;
    merge(start, mid, arr, tmp);
    merge(mid + 1, end, arr, tmp);
    retVal += Sort(start, mid, end, arr, tmp);
    return retVal;
}

public static int Sort(int start, int mid, int end, int[] arr, int[] ret) {
    if (start >= end)
        return -1;
    int revCount = 0;
    int i = start;
    int j = mid + 1;
    int k = start;// 注意 K 的起始位置，不能为0
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j]) {
            ret[k++] = arr[i++];
        } else {
            revCount += mid - i + 1;
            ret[k++] = arr[j++];
        }
    }

    if (i > mid) {
        while (j <= end) {
            ret[k++] = arr[j++];
        }
    }
    if (j > end) {
        while (i <= mid) {
            ret[k++] = arr[i++];
        }
    }

    for (int n = 0; n <= end; n++) {
        arr[n] = ret[n];
    }
    return revCount;
}

public static void main(String[] args) {
    //int[] arr = { 3, 5, 9, 2, 1, 4, 7 };
    int[] arr = {9, 2, 1, 4, 7 };
    int[] tmp = new int[arr.length];
    int ReverseCount = merge(0, arr.length - 1, arr, tmp);
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
    System.out.println("逆序数为：" + ReverseCount);

}
}

总结

归并排序还是不太熟，但是比以前好多了，现在能手写差不多，继续努力。