面试题 小和问题

面试题 小和问题"/>

面试题 小和问题

面试题 小和问题

题目：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和
例子：
[2,5,4,2]
2左边比2小的数：没有
5左边比5小的数：2
4左边比4小的数：2
2左边比2小的数：没有
小和为2+2 = 4

思路：归并
小和问题等价于找数组中每一个元素右侧有几个比当前数大的元素，sum=a[0]*num1+a[1]*num2…
可以通过归并的思想，先分解，再merge。分解至单个元素，在合并的过程中记录每个元素右侧大于当前元素的个数
特别地，当左右相等的时候，一定先拷贝右组的数，且不产生小和，因为不知道右组有多少数比左组的数大

public class SmallSum {public static void main(String[] args) {int[] arr = new int[]{3,5,5,7,4,3,4};SmallSum s = new SmallSum();System.out.println(s.smallSum(arr));}public int smallSum(int[] arr){if(arr == null || arr.length < 2) return 0;return process(arr,0,arr.length-1);}public int process(int[] arr , int left,int right){if(left == right) return 0;int mid = left + ((right - left)>>1);return process(arr,left,mid)+process(arr,mid+1,right)+merge(arr,left,mid,right);}public int merge(int[] arr , int left ,int mid ,int right){int p1 = left;int p2 = mid + 1;int sum = 0;int[] temp = new int[right-left+1];int i = 0;while(p1<=mid && p2<=right){sum += arr[p1]>= arr[p2]?0:(right-p2+1)*arr[p1];//right-p2+1,代表右侧数组中大于arr[p1]的元素个数。temp[i++] = arr[p1]< arr[p2]?arr[p1++]:arr[p2++];//左右相等的时候，一定先拷贝右组的数}while(p1<=mid){temp[i++] = arr[p1++];}while(p2<=right){temp[i++] = arr[p2++];}for(i = 0;i<temp.length;i++){arr[left+i] = temp[i];}return sum;}
}

扩展：

• 归并时间复杂度为O(nlogn),最好、最坏、平均时间复杂度均为O(nlogn)
• 归并空间复杂度为O(n）,因为每次都需要一个temp数组记录归并后的结果，最长不超过原数组长度
• 归并排序是否稳定，要看当左侧数组元素等于右侧数组元素时，如何处理；如果先将左侧元素加入temp，再将右侧元素加入temp则为稳定排序算法。在小和问题中，就是非稳定的。