8.小和问题

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
例子：
[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

递归方式归并排序中，总能递归到最小元组，那么我们可以想到，求左边比右边小的数字和，就是求左边每个比较小的数字与右边比它大的数字个数的乘积和。（比较小的含义是它的右边存在比它大的任意的数）

利用归并排序归并过程无浪费比较和不重复比较的特点对最小和问题进行加速，我们将归并排序的过程变为求左边每个比较小的数字与右边比它大的数字个数的乘积和的过程这个问题就解决了。

代码如下下：

package yzy.algorithm;

public class smallSum {
    public static int smallsum(int[] arr) {
        if(arr == null || arr.length<2)
            return 0;
        return sortProcess(arr, 0, arr.length-1);
    }

    //实际排序的递归过程
    public static int sortProcess(int[] arr, int L, int R) {
        if(L == R)
            return 0;
        int mid = ((L-R)>>1) + R;
        return sortProcess(arr, L, mid)+
        sortProcess(arr, mid+1, R)+
        merge(arr, L, mid, R);
    }

    public static int merge(int[] arr, int L, int mid, int R) {
        int[] help = new int[R-L+1];  //开辟与要排序的数组相同大小额外的空间
        int i = 0;
        int p1 = L;
        int p2 = mid+1;
        int res = 0;
        while(p1<=mid && p2<=R) {
            res += arr[p1] < arr[p2] ? (R-p2+1)*arr[p1] : 0;
            help[i++] = arr[p1]<arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while(p2<=R) {
            help[i++] = arr[p2++];
        }
        for(i=0; i<help.length; ++i) {
            arr[i+L] = help[i];
        }
        return res;
    }

    //对数器: 生成一个长度范围在[1, size]的任意长度并且任意位置是随机值的数组
    //随机值的范围在:[0, value]
    public static int[] generateRandomArray2(int size, int value) {
        //Math.random()  返回[0, 1)范围中的随机小数
        //(size+1)*Math.random()  [0, size+1)-->[0, size]
        int[] arr = new int[(int)((size+1)* Math.random())+1];  //(size+1)* Math.random()是[0, size]范围中的随机小数
        for(int i=0; i<arr.length; ++i) {
            arr[i] = (int) ((value+1)* Math.random());
        }
        return arr;
    }

    public static void showArr(int[] arr){
        for(int i=0; i<arr.length; ++i){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = generateRandomArray2(10, 11);
        System.out.print("对数器产生的数组：");
        showArr(arr);
        System.out.print("最小和：");
        System.out.println(smallsum(arr));
        System.out.print("归并排序后的数组：");
        showArr(arr);
    }
}


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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

求中间下标：

mid = ((L-R)>>1) + R;
1

是为了防溢出，同时提高运算效率(位运算比算术运算快很多，算术运算和位运算 指标都是常数，常数项算数运算大)