题解 | #计算数组的小和#

题目分析

根据左神讲的smallSum
先可以写出暴力方法：

数组 s = [1, 3, 5, 2, 4, 6] ，在 s[0] 的左边小于或等于 s[0] 的数的和为 0 ； 在 s[1] 的左边小于或等于 s[1] 的数的和为 1 ；在 s[2] 的左边小于或等于 s[2] 的数的和为 1+3=4 ；在 s[3] 的左边小于或等于 s[3] 的数的和为 1 ；

public static int comparator(int[] arr) {
        if(arr == null || arr.length < 2) {
            return 0;
        }
        int res = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                res += arr[j] <= arr[i] ? arr[j] : 0; // 小于或等于
            }
        }
        return res;
    }

暴力的解法是当前位置向左看，把所有小于等于它的数加到结果里去；反过来想，一个数字要被加几次，取决于后面有多少大于或等于它的数。例如s = [1, 3, 5, 2, 4, 6] 对于3来说，5,4,6 向左看时会导致res += 3

归并排序使子序列有序，再将子序列合并得到完整有序表的过程，可以方便地顺便去计算小和。若左边p1指向的值小于右侧p2指向的值，我们可以根据下标计算，快速得出右侧有(r - p2 + 1)大于或等于p1位置数值的数，利用归并排序的稳定性，我们可以不重复无遗漏地计算出小和。

代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型ArrayList 
     * @return long长整型
     */
    public long calArray (ArrayList<Integer> nums) {
        if(nums == null || nums.size() < 2) {
            return 0;
        }
        Integer[] arr = new Integer[nums.size()];
        nums.toArray(arr);
        return mergeSort(arr, 0, nums.size() - 1);
    }
    public long mergeSort(Integer[] arr, int l, int r) {
        if(l >= r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        return mergeSort(arr, l, mid) +
            mergeSort(arr, mid + 1, r) +
            merge(arr, l , mid, r);
    }
    public long merge(Integer[] arr, int l, int m, int r) {
        Integer[] help = new Integer[r - l + 1];
        long res = 0l;
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        while(p1 <= m && p2 <= r) {
            res += arr[p1] <= arr[p2] ? arr[p1] * (r - p2 + 1) : 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 res;
    }
}