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

问题描述

小和定义：
　　例如：数组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;
    }
}

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

原文：https://www.cnblogs.com/coding-gaga/p/10853397.html