Merge Sort

Merge Sort

时间复杂度O(nlogn), 是stable的sorting算法，空间O(n)。

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        if (A == null || A.length <= 1) {
            return;
        }

        mergeSort(A, 0, A.length - 1, new int[A.length]);
    }

    private void mergeSort(int[] A, int start, int end, int[] temp) {
        if (start >= end) {
            return;
        }

        int mid = (start + end) / 2;
        mergeSort(A, start, mid, temp);
        mergeSort(A, mid + 1, end, temp);
        merge(A, start, mid, end, temp);
    }

    private void merge(int[] A, int start, int mid, int end, int[] temp) {
        int left = start, right = mid + 1, index = start;
        while (left <= mid && right <= end) {
            if (A[left] < A[right]) {
                temp[index++] = A[left++];
            } else {
                temp[index++] = A[right++];
            }
        }

        while (left <= mid) {
            temp[index++] = A[left++];
        }
        while (right <= end) {
            temp[index++] = A[right++];
        }

        for (int i = start; i <= end; i++) {
            A[i] = temp[i];
        }
    }
}

Reverse Pairs

这题是merge sort的应用，要我们找当前的array里，如果i < j and array[i] > array[j]算一对reverse pair的话，这个array里总过有多少对reverse pair。

在merge的过程中，我们一定会比较left part里的值和right part里的值的大小，做merge。每一次遇到array[left] > array[right]的话，

当前的一个array[right]的值，配上之后所有的包括当前这个array[left]的数，都是reverse pair，总共有mid - left + 1对。

public class Solution {
    /**
     * @param A an array
     * @return total of reverse pairs
     */
    public long reversePairs(int[] A) {
        if (A == null || A.length <= 1) {
            return 0;
        }

        int[] temp = new int[A.length];
        return mergeSort(A, 0, A.length - 1, temp);
    }

    private long mergeSort(int[] A, int start, int end, int[] temp) {
        if (start >= end) {
            return 0;
        }

        int mid = (start + end) / 2;
        long left = mergeSort(A, start, mid, temp);
        long right = mergeSort(A, mid + 1, end, temp);

        return left + right + merge(A, start, mid, end, temp);
    }

    private long merge(int[] A, int start, int mid, int end, int[] temp) {
        int left = start, right = mid + 1, index = start;
        long sum = 0;
        while (left <= mid && right <= end) {
            if (A[left] <= A[right]) {
                temp[index++] = A[left++];
            } else {
                temp[index++] = A[right++];

                // update sum here
                sum += mid - left + 1;
            }
        }

        while (left <= mid) {
            temp[index++] = A[left++];
        }
        while (right <= end) {
            temp[index++] = A[right++];
        }

        for (int i = start; i <= end; i++) {
            A[i] = temp[i];
        }

        return sum;
    }
}

Count of Smaller Numbers After Self

待做