小和问题

描述

在一个数组中，每一个数左边比当前数小的累加起来，叫做这个数组的小和。求一个数组的小和。
例子：
[1，3，4，2，5]
1 左边比 1 小的数：没有；
3 左边比 3 小的数：1；
4 左边比 4 小的数：1，3；
2 左边比 2 小的数：1；
5 左边比 5 小的数：1，3，4，2；
所以小和为：1+1+3+1+1+3+4+2=16

分析

小和问题可以利用归并排序高效地求解，时间复杂度为 O(nlogn)。每一趟归并，都可以产生一个子序列的小和，最终将所有归并所得小和相加，便是原序列的小和。如上述例子中，总共需要归并四次：

由于归并过程中，两边序列是有序的，所以计算小和时，如果左边序列当前节点小于右边序列当前节点，那么右边序列当前节点之后的所有节点值都比左边当前节点大，都会产生小和。假设左边当前节点值为 x，右边当前节点之后包括自己还有 n 个节点，那么此次产生的小和就为 x * n。下图整理了每次产生小和的情况：
第一趟：

第二趟：

第三趟：

第四趟：

总共产生小和：
1+1+3+2+2+3+4=16

代码

public class smallSumProblem {
    public static void main(String[] args) {
        int[] a = {1,3,4,2,5};
        System.out.println("原序列:");
        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
        System.out.println("小和为:\n" + smallSumProblem(a));
    }
    public static int smallSumProblem(int[] a) {
        return mergeSort(a, 0, a.length - 1);
    }
    // 归并排序
    public static int mergeSort(int[] a,int begin, int end) {
        if (begin == end) {                             // base case
            return 0;
        }
        int sum = 0;                                    // 当前所有归并过程的小和
        int mid = (begin + end) / 2;                    // 子序列拆成两个更小的子序列
        sum += mergeSort(a, begin, mid);                // 当前所有归并过程的小和等于左边子序列归并的小和                                           加上右边子序列归并的小和
        sum += mergeSort(a, mid+1, end);                // 加上右边子序列归并的小和
        sum += merge(a, begin, mid + 1, end);           // 加上本趟归并的小和
        return sum;
    }
    // 归并操作
    public static int merge(int a[], int left, int right, int rightEnd) {
        int sum = 0;                                        // 本趟归并的小和
        int[] temp = new int[rightEnd - left + 1];          // 临时数组存放排序后的序列
        int idx = 0;                                    
        int leftEnd = right - 1;                        
        while (left <= leftEnd && right <= rightEnd) {
            if (a[left] < a[right]) {                       // 如果左序列当前节点小于右序列当前节点 
                sum += a[left] * (rightEnd - right + 1);    // 小和加上左序列当前节点的值 乘以 右序列当前节点之后包括当前节点的节点总数
                temp[idx++] = a[left++];                    // 左序列当前节点向后移动
            } else {                        
                temp[idx++] = a[right++];                   // 否则左序列和右序列的当前节点均向后移动一格
            }
        }
        while (left <= leftEnd) {                           
            temp[idx++] = a[left++];
        }
        while (right <= rightEnd) {
            temp[idx++] = a[right++];
        }
        for (int i = temp.length - 1; i >= 0; i--) {        
            a[rightEnd--] = temp[i];
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

out：
原序列:
1 3 4 2 5
小和为:
16