归并排序示例：小和问题_归并排序 计算左侧小于当前元素的个数

题目：

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

示例：

[1，3，4，2，5]

1：左边没有比 1 小的数。小和 = 0

3：左边比 3 小的数有 1。小和 = 1 * 1

4：左边比 4 小的数有 1，3。小和 = 1 * 1 + 1 * 3

2： 左边比 2 小的数有 1。 小和 = 1 * 1

5： 左边比 5 小的数有 1，3，4，2。 小和 = 1 * 1 + 1 * 3 + 1 * 4 + 1 * 2

总共结果 = 1 + 1 + 3 + 1 + 1 + 3 + 4 + 2 = 16

依据示例，采用 BF 的到 O(N^2) 的结果

转换下题目需求，可以看出：

对于 1 来讲，最后结果一共出现了 3，4，2，5 位置比较

对于 3 来讲，最后结果一共出现了 4，5 位置比较

对于 4 来讲，最后结果一共出现了 5 位置比较

对于 2 来讲，最后结果一共出现了 5 位置比较

对于 5 来讲，没有出现

那么可以各个元素的小和可以看作是：

与其右侧元素比较，大于自己的元素需要计算入内

1：4 * 1

3： 2 * 3

4： 1* 4

2： 1 * 2

总共结果 = 4 + 6 + 4 + 2 = 16

思维就是，以 某个元素 i 来讲，一定是某个大数的小和，所以只需要看右侧比 i 大的元素就是 i 元素存在与小和的情况

这样对于每一个数对右侧元素的比较，我们在 排序算法之归并排序  中的 merge 过程就是这样

接着我们就手推下这个过程：

归并排序分解过程图：

其中黄色部分我们要来看看

1. p(0, 1) 

        左侧（1） 与 右侧（3） 比较：

                1 < 3，1 入 help，小和为 1 * 1

        然后 3 入 help

2. p(0, 2)

        左侧(1，3） 与 右侧（4）比较：

                1 < 4 ，1 入 help ，小和为 1 * 1

                3 < 4， 3 入 help， 小和为 1 * 3

       然后 4 入 help     

3. p(3, 4) 

        左侧（2） 与 右侧（5） 比较：

                2 < 5，2 入 help，小和为 1 * 2

        然后 5 入 help

4. p(0, 4)

        左侧（1，3，4） 与 右侧（2，5）比较：

                1 < 2，1 < 5，1 入 help，小和为 2 * 1

                3 > 2，2 入 help

                3 < 5，3 入 help，小和为 1 * 3

                4 < 5，4 入 help，小和为 1 * 4

                5 入 help

总的小和 =  1 * 1 + 1 * 1+ 1 * 3 + 1 * 2 +  2 * 1 + 1 * 3 + 1 * 4 = 16               

代码实现部分有少许改变：

1. （新增） 如果左侧比右侧小，那么就要计算小和

2. 拷贝到 help，注意要先拷贝右侧，再拷贝左侧（当出现数值一样的时候才能有效计算）

以上图 1 为例，只有先拷贝完成右侧等值 1 时，右侧 5 开始的数据才是 大于 1 的数值，直接用下标计算总共有多少个大于 1 的个数 

	while(p1 <= mid && p2 <= r)
	{
		ret += 	arr[p1] >= arr[p2] ? 0 : (r - p2 + 1) * arr[p1];
		help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];		// note: if equal, copy right side first
	}

 3. 计算总的小和 = 左侧排好序的小和 + 右侧排好序的小和 + 左右侧合并的小和

int doMergeSort(int *arr, int l, int r)
{
	if(l == r)
		return 0;
	
	int mid = l + ((r - l) >> 1);
	
	return doMergeSort(arr, l, mid) + doMergeSort(arr, mid+1, r) + mergeArr(arr, l, mid, r);
}

依据示例，采用 归并排序 的到 O(N * logN) 的结果

思考下：

1. 是否必须进行排序

2. 对于一个元素来讲是否存在漏算情况

问题1：

        我们可以看见只有排序完成，才能用下标差计算比当前元素大的个数

问题2：

        以一组数来讲，比如：{a，b，c，d，e，f，g}

        c 元素经过的路径：

                1. 与有序和（a，b）进行比较，因为 c 是右侧，并不进行小和计算

                2. 然后组成（a，b，c）组合，至于 c 的具体位置并不重要

                3. 然后与右侧方向的子集逐一合并

        所以不会漏算

 

更多数据结构算法详解