小和问题及扩展

一、写作本篇文章的目的

本篇主要讲述如何用递归法求解小和问题，以及小和问题类似的一类问题。

二、小和问题

【题目】求一个数组的小和。

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

【算法分析】

比如想要求解数组[1,3,4,2,5]的小和：

1、根据定义设计的算法

直接根据定义，从左往右遍历，每个数值都求出它的小和，并累加求解：
1左边比1小的数：没有
3左边比3小的数：1
4左边比4小的数：1,3
2左边比2小的数：1
5左边比5小的数：1,3,4,2
所以小和为1+1+3+1+1+3+4+2=16

参考代码C++:

int GetSum(const vector<int>& arr)
{
	int sum = 0;
	for (int i = 0; i < arr.size(); ++i)
	{
		int temp = arr[i];
		for (int j = 0; j < i; ++j)
		{
			if (arr[j] < temp)
			{
				sum += arr[j];
			}
		}
	}
	return sum;
}

此算法简单易懂，但是时间复杂度为O(n^2)，但这并不是我们想要讲的算法。

2、递归法求解

还是求解数组[1,3,4,2,5]的小和，我们可以换个思路：

1的右侧有4个数比1大：则 sum += 1 * 4

3的右侧有2个数比3大：则 sum += 3 * 2

4的右侧有1个数比4大：则 sum += 4 * 1

2的右侧有1个数比2大：则 sum += 2 * 1

最后sum = 16

为什么可以这样求解？因为我们在求解小和的过程中，根据定义法：如果左侧某数a比右侧某数b小，则在求b的小和的时候，肯定会累加一个a，即sum+=a。反过来，在遍历到a的时候，如果我们知道右侧有几个数比a大，则可以提前知道会累加几个a。

根据描述，这种思路如果还是用遍历法，则还是时间复杂度为O(N^2)的算法。我们需要用更加优质的算法处理这个思路-递归。

算法详述：

我们知道递归方法为一个数组排序只需要O(N*logN)的时间复杂度。而排序有个merge的过程，

左侧：1        右侧：3      merge：   因为1 < 3，        产生1*1=1的小和

左侧：1,3     右侧：4      merge：   因为1<4,     产生1*1=1的小和

                                                        因为3<4，产生3*1=4

左侧：2        右侧：5      merge：   因为2<5，          产生2*1的小和

左侧1,3,4      右侧：2,5  merge：   因为1<2,            产生1*2（右侧>=2的共2个数）= 2 的小和

                                                        因为 3<5,           产生3*1=3 的小和

                                                        因为 4<5,           产生4*1=4 的小和

总小和=16

总体上来说，还是上面的思路，只是把求右侧比某个数大的过程拆分了几步，但是由于比较过程没有重复，甚至由于排序了，还减少了一部分比较，所以是更优的。

比如求比1大的数我们知道有4个，分别是3,4,2,5，而递归时，我们只比较了3,4,2就得出了4个1的结论。

总之这个算法可能不是很好理解。我代码的注释写的很详细，大家可以参考，如果还是不理解可以参考最下面分享的视频讲解。

参考代码（C++实现）

//只有每次merge的时候才会计算小和并且排序
int merge(vector<int>& arr, int L, int R, int M)
{
	//创建一个临时的合并数组，临时存放排序后的L--R之间的元素
	vector<int> merArr(R - L + 1);
	int p1 = L; //“左侧”元素的指针，“左侧”数组范围从L--M
	int p2 = M + 1; //“右侧”元素的指针，“右侧”数组范围从M+1--R
	int i = 0; //merArr的指针
	int sum = 0; //保存此次merge产生的小和
 
	//如果M+1 == p1“左侧”越界；如果R+1 == p2“右侧”越界
	while (p1 <= M && p2 <= R )
	{
		//p1 < p2会产生小和
		if (arr[p1] < arr[p2])
		{
			//因为右侧数组有序，如果arr[p2]比arr[p1]大，则p2位置的所有数据都会比arr[p1]大，则一共会产生R-p2+1个arr[p1]的小和
			sum += arr[p1] *(R-p2+1);
			//合进排序数组
			merArr[i++] = arr[p1++];
		}
		else
		{
			//合进排序数组
			merArr[i++] = arr[p2++];
		}
		//merArr[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
	}
	//如果“右侧”数组已经合完，则不会再产生小和，把所有“左侧”数组合进排序数组
	while (p1 <= M)
	{
		merArr[i++] = arr[p1++];
	}
	//如果“左侧”数组已经合完，则不会再产生小和，把所有“右侧”数组合进排序数组
	while (p2 <= R)
	{
		merArr[i++] = arr[p2++];
	}
	//已经排好序，把排序结果反填充进入arr数组
	for (int it : merArr)
	{
		arr[L++] = it;
	}
 
	//返回小和
	return sum;
}
 
//排序并且得到阶段性的小和
int Process(vector<int>& arr, int L, int R)
{
	if (L == R)
	{
		return 0;
	}
 
	int mid = L + ((R - L) >> 1);
	return Process(arr, L, mid) + Process(arr, mid + 1, R) + merge(arr, L, R, mid);
}
 
//求解小和
int smallSum(vector<int>& arr)
{
	if (arr.size() < 2)
	{
		return 0;
	}
 
	return Process(arr, 0, arr.size() - 1);
}

【复杂度分析】

根据master公式，此算法的时间复杂度为 T（N） =  2 * T（N/2）+ O(N)

a=2,b=2,d=1   log(b,a)=0 == d , 则时间复杂度为 O(N*logN)

因为merArr为额外开辟的空间，最大为N，则空间复杂度为O(N)

三、小和问题扩展

小和问题是一个比较经典的问题。我们有一系列问题可以使用上述求小和问题的递归方法求解。

1、逆序对问题

【题目】一个数组中，如果某数A的右侧存在一个数B比A小，即A>B，则{A，B}是一个逆序对。求一个数组中有多少对逆序对（使用递归法求解）。

【分析】同上述小和问题

参考代码

其他函数的实现不需要变，只需要修改merge函数即可

//只有每次merge的时候才会计算逆序个数并且排序
int merge(vector<int>& arr, int L, int R, int M)
{
	//创建一个临时的合并数组，临时存放排序后的L--R之间的元素
	vector<int> merArr(R - L + 1);
	int p1 = L; //“左侧”元素的指针，“左侧”数组范围从L--M
	int p2 = M + 1; //“右侧”元素的指针，“右侧”数组范围从M+1--R
	int i = 0; //merArr的指针
	int sum = 0; //保存逆序对个数
 
	//如果M+1 == p1“左侧”越界；如果R+1 == p2“右侧”越界
	while (p1 <= M && p2 <= R )
	{
		//arr[p1] > arr[p2]会产生逆序
		if (arr[p1] > arr[p2])
		{
			sum += R - p2 + 1; //一旦arr[p2]<arr[p1]，则右侧中p2后面的数都小于arr[p1]
			//打印逆序对
			for (int r = p2; r < R + 1; ++r)
			{
				cout << arr[p1] << "," << arr[r] << endl;
			}
			//合进排序数组（降序排列）
			merArr[i++] = arr[p1++];
		}
		else
		{
			//合进排序数组
			merArr[i++] = arr[p2++];
		}
		//merArr[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
	}
	//如果“右侧”数组已经合完，则不会再产生小和，把所有“左侧”数组合进排序数组
	while (p1 <= M)
	{
		merArr[i++] = arr[p1++];
	}
	//如果“左侧”数组已经合完，则不会再产生小和，把所有“右侧”数组合进排序数组
	while (p2 <= R)
	{
		merArr[i++] = arr[p2++];
	}
	//已经排好序，把排序结果反填充进入arr数组
	for (int it : merArr)
	{
		arr[L++] = it;
	}
 
	//返回
	return sum;
}

四、总结

个人认为上述小和问题和逆序数问题，具有如下规律：

1、以某个数A为基准，需要在A之后寻找达成某个条件（比A大或比A小）的数；

2、这个A需要整体数组（设为arr）遍历一遍，用代码来说，A的值是这样的 for(auto A : arr）；

如果待解问题可以用上诉思路解释，我们就可以考虑是否能够使用递归法求解。

【参考&致谢】

一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV13g41157hK?p=3