数组小和

package class04;

/**
 * 数组小和
 * 在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来叫数组的小和，求数组小和
 */
public class Code02_SmallSum {
    public static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    public static int process(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        int M = L + ((R - L) >> 1);
        return process(arr, L, M)//左组产生的最小和
                + process(arr, M + 1, R)//右组产生的最小和
                + merge(arr, L, M, R);//合并产生的最小和
    }

    //合并
    private static int merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];//定义一个help数组，长度位(R - L + 1)
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        int ans = 0;
        while (p1 <= M && p2 <= R) {
            //在给help数组赋值之前，累加ans。
            //如果arr[p1] < arr[p2]，那么ans就累加上(R - p2 + 1)个arr[p1]
            //否则就累加0个arr[p1]
            ans += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
        return ans;//返回当前循环的merge方法中的ans。
    }

    //对数器
    //遍历每一个数，并把所有，在当前循环中的这个数左侧的，并且比这个数小的数，都相加。
    public static int comparator(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int ans = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                ans += arr[j] < arr[i] ? arr[j] : 0;
            }
        }
        return ans;
    }

    public static int[] generatorRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) (Math.random() * maxSize) + 2];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * maxValue);
        }
        return arr;
    }

    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public static void main(String[] args) {
        int maxSize = 100;
        int maxValue = 100;
        int testTimes = 100000;
        System.out.println("test start!");
        for (int i = 0; i < testTimes; i++) {
            int[] arr0 = generatorRandomArray(maxSize, maxValue);
            int[] arr1 = copyArray(arr0);
            int[] arr2 = copyArray(arr0);
            int i1 = smallSum(arr1);
            int i2 = comparator(arr2);
            if (i1 != i2) {
                System.out.println("oops!");
                System.out.println("i1 = " + i1);
                System.out.println("i2 = " + i2);
                break;
            }
        }
        System.out.println("test end!");
    }

}