小和问题
小和问题：在一个数组中，每个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。
例子：数组[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,6,8,4,5}; int ss=smallSum(arr); System.out.println(ss); } 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 m,int r){ //辅助空间 int[] help=new int[r-l+1]; int i=0,p1=l,p2=m+1; int res=0; //都不越界 while (p1<=m && p2<=r){ //边界值判断，如果左右两侧值相等的话，应该是右侧指针右移 res+=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 (int j=0;j<help.length;j++){ arr[l+j]=help[j]; } return res; } }
逆序对问题
题目描述：
题解：
public class nxd { public static void main(String[] args) { int[] arr={7,5,6,4}; int ss=smallSum(arr); System.out.println(ss); } 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 m,int r){ //辅助空间 int[] help=new int[r-l+1]; int i=0,p1=l,p2=m+1; int res=0; //都不越界 while (p1<=m && p2<=r){ //边界值判断，如果左右两侧值相等的话，应该是右侧指针右移 res+=arr[p1]>arr[p2]?(m-p1+1):0; help[i++]=arr[p1]>arr[p2]?arr[p2++]:arr[p1++]; } //有一侧越界 while (p1<=m){ help[i++]=arr[p1++]; } while (p2<=r){ help[i++]=arr[p2++]; } for (int j=0;j<help.length;j++){ arr[l+j]=help[j]; } return res; } }
