[程序员代码面试指南]数组和矩阵-计算数组的小和(归并排序)

问题描述

小和定义：
　　例如：数组s = [1, 3, 5, 2, 4, 6]，在s[0]的左边小于或者等于s[0]的数的和为0，在s[1]的左边小于或等于s[1]的数的和为1，在s[2]的左边小于或等于s[1]的数的和为1+3=4……将所有位置的左边比它小或者等于的数的和相加起来就是小和。 s的小和=0+1+4+1+6+15=27
　　给定一个数组，实现函数返回s的小和。

解题思路

• 与求数组中逆序对的问题类似，在归并排序的过程中累加小和。（笔者选择设定在升序排过程中。）

关于归并排序

• arr[l,r]是包含l及r位置对应的元素的.
• 时间复杂度O(nlogn),空间复杂度O(n).
• 归并排序实现过程为：对左右子数组分别排序，然后把左右子数组有序拷贝到copy使其有序，传参时copy数组和data数组互换传入。

注意

• 使用滚动数组时，一定要最开始初始化copy数组为原数组的拷贝，否则当只有一个元素时，就会把copy数组的原始元素传入array。
• 此题若arr[i]<=arr[j],则arr[i]比arr[j]及其后面的元素都要小，即以i为标杆，故此次合并增加的小和为arr[i]*(r-j+1)。之后计算小和的数对时不算左边是arr[i]了，所以要把arr[i]放入copy数组。又因为arr[i]<=arr[j],所以从左往右填copy数组，i、j、copy的指针都初始化为对应数组最左边。
• copyIdx的初始化要初始化为l而不是0。

代码

import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		int[] arr= {1,3,5,2,4,6};
		int[] copy=new int[arr.length];
		System.arraycopy(arr, 0, copy, 0, arr.length);//!!!
		int smallSum=getSmallSum(arr,copy,0,arr.length-1);
		System.out.println(smallSum);
	}
	
	public static int getSmallSum(int[] arr,int[] copy,int l,int r) {
		if(l==r) {
			return 0;
		}
		int mid=(l+r)>>1;
		int leftSum=getSmallSum(copy,arr,l,mid);
		int rightSum=getSmallSum(copy,arr,mid+1,r);
		
		int i=l;
		int j=mid+1;
		int copyIdx=l;//
		int smallSum=0;
		
		while(i<=mid&&j<=r) {
			if(arr[i]>arr[j]) {
				copy[copyIdx++]=arr[j++];
			}
			else {
				smallSum+=arr[i]*(r-j+1);//
				copy[copyIdx++]=arr[i++];
			}
		}
		while(i<=mid) {
			copy[copyIdx++]=arr[i++];
		}
		while(j<=r) {
			copy[copyIdx++]=arr[j++];
		}
		return smallSum+leftSum+rightSum;
	}
}