问题:小和问题
-
在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和,求一个数组的小和
-
举例
如 [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 -
思路:采用归并排序的方式,在归并排序的过程中同时计算小和的问题,java实现如下:
package problem;
public class SmallSum {
public static int merge(int[] arr,int left,int mid,int right)
{
int[] arr_new=new int[right-left+1];
int i=0;
int p1=left;
int p2=mid+1;
int res=0;
while(p1<=mid && p2<=right)
{
res+=arr[p1]<arr[p2]?(right-p2+1)*arr[p1]:0;
arr_new[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
}
while(p1<=mid)
{
arr_new[i++]=arr[p1++];
}
while(p2<=right)
{
arr_new[i++]=arr[p2++];
}
for(int j=0;j<arr_new.length;j++)
{
arr[left+j]=arr_new[j];
}
return res;
}
public static int getSmallSum(int[] arr,int left,int right)
{
if(arr==null || arr.length<2 || left==right)
{
return 0;
}
int mid=left+((right-left)>>1);
return getSmallSum(arr,left,mid)+getSmallSum(arr,mid+1,right)+merge(arr,left,mid,right);
}
public static void main(String[] args) {
int[] arr={1,3,4,2,5};
int sum=getSmallSum(arr,0,arr.length-1);
System.out.println(sum);
}
}
执行结果为:
16