问题描述
在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。
举个栗子
{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 void main(String[] args) {
int[] arr = {3,2,1,7,6,8,9,0,5};
System.out.println(smallSum(arr));
}
public static int smallSum(int[] arr){
if(arr==null||arr.length<2){
return 0;
}
return mergeSort(arr,0,arr.length-1);
}
public static int mergeSort(int[] 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 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 sum = 0;
while(p1 <= mid && p2 <= R){
sum += arr[p1] < arr[p2] ? arr[p1]*(R-p2+1) : 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[L+i] = help[i];
}
return sum;
}
}
上述代码与归并排序的代码多了这个sum += arr[p1] < arr[p2] ? arr[p1]*(R-p2+1) : 0; ,其他的逻辑是完全一样的。
为什么这样求出来的就是小和?
1、将一个数组不断划分,划分成左右两个子集,最终划分为最小子集,两边各一个数的时候划分结束;
2、左右两个数比较,如果左边子集的那个数小于右边子集的那个数,那么就算进小和里面,紧接着会有一个归并排序的排序过程(如果是左边小当然不会发生变化),这样最小子集的数的小和算出来了,也排好序了;然后和这两个数同时划分的另外两个子集中也进行一样的操作,那么另外一侧的小和也算出来了,顺序也排好了(当然一个数就没有可以直接和之前排好的比较,内部就没有排序求小和了)
3、假如说通过2的操作,现在分别是两组内部有两个数的子集,那么又因为这两个子集是同一级(同一次分组形成的),这两个内部数据是有序的,右侧子集的第一个数字和左侧子集的第一个数字比较,如果右侧第一个就比左侧第一个大,那么右侧两个数字都比第一个数字大,则(左侧数字*2)就是此次小和的一部分了(其中2是([右侧子集R]-[右侧第一个数字的下标])+1),然后开始和左侧第二个数字比较,依次下去。这也就是上述多出的那一行代码的逻辑。
上述解释总归是文字,描述上理解上会有出入,拿一组具体的数字来配合上述解释:
归并排序求小和图解.pngend
网友评论