數(shù)組小和的定義如下：例如，數(shù)組s=[1,3,5,2,4,6]
在s[0]的左邊小于或等于s[0]的數(shù)的和為0
在s[1]的左邊小于或等于s[1]的數(shù)的和為1
在s[2]的左邊小于或等于s[2]的數(shù)的和為1+3=4
在s[3]的左邊小于或等于s[3]的數(shù)的和為1
在s[4]的左邊小于或等于s[4]的數(shù)的和為1+3+2=6
在s[5]的左邊小于或等于s[5]的數(shù)的和為1+3+5+2+4=15
所以s的小和為0+1+4+1+6+15=27
給定一個(gè)數(shù)組s，實(shí)現(xiàn)函數(shù)返回s的小和涂乌。

對(duì)于本題埂淮，最容易想到的就是通過(guò)二重循環(huán)暴力求解寄雀，時(shí)間復(fù)雜度O(n^2)炒俱，代碼如下：

public class ArraySmallSum {

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 2, 4, 6};
        int smallSum = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    smallSum += arr[j];
                }
            }
        }
        System.out.println(smallSum);
    }
}

這樣的時(shí)間復(fù)雜度顯然是不能令人滿意的巷燥，這里我們利用歸并排序赡盘，在對(duì)有序子數(shù)組進(jìn)行merge的同時(shí)，累加數(shù)組小和缰揪，時(shí)間復(fù)雜度O(nlogn)陨享，代碼如下：

public class ArraySmallSum {

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 2, 4, 6};
        System.out.println(getSmallSum(arr));
    }


    public static int getSmallSum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return mergeSortRecursion(arr, 0, arr.length - 1);
    }

    /**
     * 遞歸實(shí)現(xiàn)歸并排序
     *
     * @param arr
     * @param l
     * @param r
     * @return 返回?cái)?shù)組小和
     */
    public static int mergeSortRecursion(int[] arr, int l, int r) {
        if (l == r) {   // 當(dāng)待排序數(shù)組長(zhǎng)度為1時(shí)，遞歸開(kāi)始回溯钝腺，進(jìn)行merge操作
            return 0;
        }
        int mid = (l + r) / 2;
        return mergeSortRecursion(arr, l, mid) + mergeSortRecursion(arr, mid + 1, r) + merge(arr, l, mid, r);
    }

    /**
     * 合并兩個(gè)已排好序的數(shù)組s[left...mid]和s[mid+1...right]
     *
     * @param arr
     * @param left
     * @param mid
     * @param right
     * @return 返回合并過(guò)程中累加的數(shù)組小和
     */
    public static int merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];    // 輔助存儲(chǔ)空間 O(n)
        int index = 0;
        int i = left;
        int j = mid + 1;
        int smallSum = 0;       // 新增抛姑，用來(lái)累加數(shù)組小和
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                // 當(dāng)前一個(gè)數(shù)組元素小于或等于后一個(gè)數(shù)組元素時(shí)，累加小和
                // s[i] <= s[j] -> s[i] <= s[j]...s[right]
                smallSum += arr[i] * (right - j + 1);
                temp[index++] = arr[i++];
            } else {
                temp[index++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[index++] = arr[i++];
        }
        while (j <= right) {
            temp[index++] = arr[j++];
        }
        for (int k = 0; k < temp.length; k++) {
            arr[left++] = temp[k];
        }
        return smallSum;
    }
}

叛藓客網(wǎng)有道數(shù)組單調(diào)和定硝，實(shí)際上和該題為同一道題。
另一道數(shù)組中的逆序?qū)?/a>毫目，與該題解法類(lèi)似蔬啡，只是merge時(shí)逆序?qū)Φ睦奂訔l件和算法有所不同，此時(shí)merge操作的代碼如下：

/**
 * 合并兩個(gè)已排好序的數(shù)組s[left...mid]和s[mid+1...right]
 *
 * @param arr
 * @param left
 * @param mid
 * @param right
 * @return 返回合并過(guò)程中累加逆序?qū)? */
public static int merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];    // 輔助存儲(chǔ)空間 O(n)
    int index = 0;
    int i = left;
    int j = mid + 1;
    int inverseNum = 0;       // 新增蒜茴，用來(lái)累加數(shù)組逆序?qū)?    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[index++] = arr[i++];
        } else {
            // 當(dāng)前一個(gè)數(shù)組元素大于后一個(gè)數(shù)組元素時(shí)星爪，累加逆序?qū)?            // s[i] > s[j] -> s[i]...s[mid] > s[j]
            inverseNum += (mid - i + 1);
            temp[index++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[index++] = arr[i++];
    }
    while (j <= right) {
        temp[index++] = arr[j++];
    }
    for (int k = 0; k < temp.length; k++) {
        arr[left++] = temp[k];
    }
    return inverseNum;
}