06、小和问题_c++在一个数组中,每一个数左边比当前数小(不包括相等的情况)的数累加起来,叫做这

一、小和问题

1.1 问题简介

        在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组
的小和。

         例子：如数组[1,3,6,2,5]

        1左边比1小的数，没有；
        3左边比3小的数，1；
        6左边比4小的数，1、3；
        2左边比2小的数，1；
        5左边比5小的数，1、3、2；
        所以小和为1+1+3+1+1+3+2=12

1.2 思路

常规解法，进行两次for循环嵌套，时间复杂度为：O(N²)。通过归并排序的方法将时间复杂度降到O(nlogn)。

        归并排序分两步，一是分，二是治。分好说，不停的将数组划分为两部分。（可以看前一篇笔记：05、归并排序及其复杂度分析_ZHY_ERIC的博客-CSDN博客）

        如下图：

        如上图，对数组进行分，接下来是治：

        （1）首先1和3进行merge，在此过程中产生小和1；

        （2）然后1,3和6进行merge，在此过程产生小和1和3；

        （3）然后2和5进行merge，在此过程产生小和2；

        （4）最后1，3，6和2，5进行merge，

               1比2，5的小和2小，一共产生n个1的小和，n就是当前右边数的个数，这里是2.所以产生2个1的小和，将1填入辅助数组。

               接着3和2比较，3>2,但是2是右边的数，不算小和。然后3和5比较，3<5，产生n个3的小和，因为此时右边只有一个数，n=1,故产生1个3的小和。

               接着6和2比较，6>2,不产生小和。6和5比较，6>5,不产生小和。

 1.3 代码

package basic_package_01;
 
public class Code_12_SmallSum {
	
	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);
		System.out.println("下标号："+mid+"数值："+arr[mid]);
		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;
		int p1 = l;
		int 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 (i = 0; i < help.length; i++) {
			arr[l + i] = help[i];
		}
		return res;
	}
 
 
	// for test
	public static void printArray(int[] arr) {
		if (arr == null) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		int[] arr = {1,3,6,2,5};
		System.out.print(smallSum(arr));
	} 
 
}

结果：