体育彩票销售站联盟

睡前故事:如何从一个数组分割出两个平均值相等的子数组

扬州计划2018-12-16 15:16:14


LeetCode Weekly Contest 77的前三题非常简单,不用带脑子直接上去暴力码几行就能解决,所以这周就不在公众号上发详细的题解了,有兴趣可以点击阅读原文去我的笔记仓库看完整的题解。这里只讨论一下最后一题即Problem

805: Split Array With Same Average相关问题,写的不专业不严谨,只是完全放松状态下想到什么说什么,就当是给关注我的人讲睡前故事吧。


问题的原描述为:

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

Example :

Input: [1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7],
and both of them have the average of 4.5.


不用看见洋文就头大,像我这样没文化的老实人直接抓住题意就行:把A分成两个无重叠的部分B和C(顺序无关),要求B和C的平均值相等。怎么样?看上去敲简单的问题吧?我还标题党了一下,这题只要求你判断有没有这样的分割,而不是具体让你把这些分割都找出来。如果没有时间和空间的限制,直接穷举从A取(2^n-2)/2个非空真子集计算平均值是否和A的平均值相同就行。


所以看到这里,差不多就明白这个问题让人头疼的地方在哪了,按照朴素的直觉去解决将面临o(2^n)级的复杂度。是的,这个看上去敲简单的问题实际上是NP完全问题——子集和问题(subset sum problem)的一个变体,原问题为给出一个数组,能否找到一个非空的和为零的子集,这是一个已经讨论了几十年的问题,我们的平均值问题可以轻易的通过给每个元素减去A的均值转换(reduce)到这个子集和问题上,同样还有很多不痛不痒的原问题的变体(等价问题):能否找出和为某个整数值s的非空子集?能否找到使两个子集和相等的划分……总之,这些都是在多项式复杂度算法不可解决的问题,精确的解需要指数级的复杂度,这类问题也可以被看成背包问题(knapsack problem)的一个特例


在了解“这是一个NP完全问题”的背景下去看待这个问题,接下来大概需要回想一下解决一般的NP完全问题会使用哪些策略:

  1. 找出容易计算的特例(Identify computationally tractable special cases)

  2. 应用启发式算法(Heuristics Algorithm)

  3. 更简单一些的指数级暴力搜索(Brute-force Search)


所以说几乎不会有哪个小傻瓜直接用那个一股脑儿瞎枚举的指数级暴力搜索嘛,好歹先稍微看看能不能写的简单点,毕竟这个问题本身那么简单啊(笑)。这里让我们先来简单的讲一下第三种,毕竟我在自己blog贴的题解和提交的解法就是服从的第三种策略原则。


思路比较简单,先假设这样的子集存在:既然sum(A)/len(A)=sum(B)/len(B)这两个“比例”的最简形式相同,C又不能是空集,所以sum(A)/len(A)一定是需要“化简约分”的,那么sum(A)和len(A)存在一个大于1的最大公约数g=gcd(sum(A),len(A)),sum(B)/len(B)被“约分”掉的那个整数必然是在(0,g)之间的,如果我们记为i,那么需要找的只是符合sum(B)=i*sum(A)/g和len(B)=i*len(A)/g的所有B,限定了子集大小以后找目标就容易多了。由于B和C是对称的,i的取值域还能再缩减一半。寻找目标B时,可以先将A按照降序排序,在A中决定取哪几个元素,从大到小按照取这个值与否进行分支的DFS,访问到比当前目标均值还小的元素时该路径必然无效可以跳出。这样修剪后(pruned)的DFS本质还是DFS,依然是指数级的复杂度,但在平均情况的输入下表现不算太坏,完全可以通过。


回到我们前面所说的结论:这个问题是背包问题的一个特例。再看一下应对NP完全问题的第一个原则,可以在问题的形式上找容易突破的特例。众所周知,在数据形式为整数时的背包问题,如果背包容量是个不大的整数,可以从容量下手做动态规划,这种想法就是“找出容易计算的特例”的一个典型体现。所以接下来去讨论我们的问题,可以看成是一个“特例的特例”。所以还是可以像背包问题一样用DP解决,根据sum(A)*len(B)%len(A)=0和对称性可以修剪出所有(0,len(A)/2)内可能的len(B),我们可以借助一个len(A)*(len(A)/2)的dp数组,其中每个dp[i][j]为一个集合,表示A[0:i]取j个数的所有可能的和值。容易得出递推式 dp[i+1][j]=dp[i][j] \cup (dp[i][j-1] + A[i+1]),找到集合dp[i][j]里是否存在满足除以j等于A的均值的元素问题即可解出。这里每次更新dp[i][j]的计算是基于和值的hash表(i.e.集合),假设A的最大元素值为M,那么每次计算dp[i][j]的时间复杂度为M*j,因为i和j取值上限都与len(A)一次线性相关,所以最终容易得出算法的总复杂度为o((len(A))^3*M),只要M不是特别巨大,也算从指数级的问题中“解脱”了。


至于第二条原则,适当运用启发式算法,这是在面对NP完全问题时比较容易想到的救命稻草,而且对问题形式的要求没那么高,总能有奇怪的启发式算法可以适用于不同的问题,这里我就不再去讨论在这个问题上的体现了,留给大家想象吧。


(今日睡前故事写的有点晚,大家晚安好梦,可惜不会发语音,我也想给大家念一句甜甜的おやすみなさい,奈何我声音不好听,我也很绝望啊.jpg)