小和问题(归并排序解法)_小和问题(sum) 在一个数组中,每一个数左边比当前数小

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组 的小和。

例子:

[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

解题思路: 求一个数左边比它小的数的和,等于求这个数组中,当前数 * 当前数右边比它大的数的个数.

利用归并排序解题,代码如下:

public class SmallSum {
    public static int smallSum(int [] arr){
 
        if (arr == null && arr.length < 2){ return -1; }
        return smallSum(arr,0,arr.length -1);
    }
 
    public static int smallSum(int [] arr, int l,int r){
 
        if (l == r) { return 0; }
        int mid = l + ((r - l) >> 1);
 
        return smallSum(arr,l,mid) + smallSum(arr,mid + 1 , r) + merge(arr,l,mid,r);
    }
 
    public static int merge(int [] arr, int l, int m, int r){
 
        int [] temp = new int [r - l + 1] ;
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        int res = 0;
 
        while(p1 <= m && p2 <= r){
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0 ;
            temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= m){
            temp[i++] = arr[p1++];
        }
        while(p2 <= r){
            temp[i++] = arr[p2++];
        }
        for (i = 0; i < temp.length ; i ++){
            arr[l + i] = temp[i];
        }
 
        return res;
    }
}