「LeetCode 805. Split Array With Same Average」解题报告

发表于 | 分类于 ， ，

题目信息

题目分析

描述

给定N个整数，判断是否能分成均值相同的两堆（非空），N范围为1到30，数值范围为0到10000。
比如样例 [1,2,3,4,5,6,7,8] 可以分成 [1,4,5,8] 和 [2,3,6,7] 两组，均值为4.5。

解题思路

初看题目直觉是NP的，看完数据范围更加确定了这一点，暴搜复杂度 $2^{30}$，不好剪枝，显然会TLE。
首先N=1时一定返回false，因为无论怎么分总有一堆为空，于是只需考虑N≥2。
先将这组数字分成数量相同的两堆，N为奇数时任意一堆多放一个即可。
暴搜出两堆各自能产生的所有组合的均值，复杂度为 $2^{15}$。
如果存在一个合理的分法满足题目要求，那么最终结果的两堆数字的均值应该都等于整组数据的均值。
此时要么在某一堆里能计算出这个均值，要么从两堆里各取一组加权平均后等于这个均值。
如果尝试两两组合算出所有的可能性，那么复杂度依旧为 $(2^{15})^2=2^{30}$。
有一个直观的想法是，两个堆算出的均值结果进行排序。
用两个指针分别指向一个堆均值的最小值（小堆），以及另一个堆均值的最大值（大堆）。
若当前指针指向的两组数加权平均比总体均值要大，那么将大堆指针往小的方向移，否则将小堆指针往大的方向移。
这样就只需要线性的复杂度扫描了，但这样做的前提是指针移走后的值不会继续用到了。
实际实现这个算法提交后发现WA了，分析一波错的数据，发现这个做法会出现问题的原因在于，可能出现这种情况：
例如小堆中目前指向的那组数个数非常多，而大堆中目前以及往小方向的连续几组数个数都比较少。
在此时算出的加权均值小于总体均值，由于小堆的一方数量上的优势会使大堆的指针往小方向连续移好几个。
若此时算出的加权均值又大于了总体均值，且小堆中往大方向连续几组数个数都更少，
那么小堆的指针又会往大的方向移很多个，那么可能在两次连续移动的中间分别存在一组数能凑成最终的答案。
一个解决这个问题的方法是，一开始将数据都去均值化。
如果存在一个合理的分法，那么最终结果的两堆数字的均值应该都等于0，等价于和为0。
如果将均值考虑成求和，那么上面说到的问题就不存在了，因为数量只对加权平均有影响，而对求和没有影响。
可以简单的证明，一旦指针移走，前面的值就不会再考虑到了。
因此上面的算法，将所有求平均的地方换成求和，这个问题就可以圆满解决了。

细节处理

  1. 虽然浮点数在乘除法上的迭代不多，但是还是要用相差在一定精度范围来判断两个浮点数是否相等。
  2. 在考虑从两堆和里面各取一部分时，可能出现在两堆中都取了全部的数字，此时形成的另一堆会是空集。
    要解决这个问题还是要记录组成当前和的元素个数，若求和的两组数的数量之和等于N了就跳过。

复杂度分析

考虑排序在内，时间复杂度为 $O(2^{N/2}\log 2^{N/2})=O(\frac{N}{2}\cdot2^{N/2})$。
N为数组长度，在N≤30时是可以接受的。
空间复杂度为 $O(2^{N/2})$。

AC代码（C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
public:
	static const int N = 35;
	const double EPS = 1e-6;

	double a[N];
	int n;
	double res;

	bool splitArraySameAverage(vector<int>& A) {
		n = (int)A.size();
		res = 0;
		for (int i = 0; i < n; ++i) {
			res += A[i];
		}
		res /= n;
		for (int i = 1; i <= n; ++i) {
			a[i] = A[i - 1] - res;
		}
		return work();
	}

	struct node {
		double sum;
		int cnt;
		node(double _sum = 0, int _cnt = 0) : sum(_sum), cnt(_cnt) {
		}
		bool operator < (const node &r) const {
			return sum < r.sum;
		}
	};

	void dfs(int p, int ed, vector<node> &adj, double sum, int cnt) {
		if (p == ed + 1) {
			if (cnt != 0) {
				adj.emplace_back(sum, cnt);
			}
			return;
		}
		dfs(p + 1, ed, adj, sum + a[p], cnt + 1);
		dfs(p + 1, ed, adj, sum, cnt);
	}

	bool my_equal(double x, double y) {
		return fabs(x - y) < EPS;
	}

	bool work() {
		if (n < 2) {
			return false;
		}
		int m = n / 2;
		vector<node> left, right;
		dfs(1, m, left, 0, 0);
		dfs(m + 1, n, right, 0, 0);
		sort(left.begin(), left.end());
		sort(right.begin(), right.end());
		int u = 0, v = (int)right.size() - 1;
		for (int i = 0; i < left.size(); ++i) {
			double avg = left[i].sum;
			if (my_equal(avg, 0)) {
				return true;
			}
		}
		while (u < (int)left.size() && v >= 0) {
			int tot = left[u].cnt + right[v].cnt;
			double avg = left[u].sum + right[v].sum;
			if (my_equal(avg, 0) && tot != n) {
				return true;
			}
			else if (avg < 0) {
				++u;
			}
			else {
				--v;
			}
		}
		return false;
	}
};

解题心得

最近在前室友的带领下刚入坑LeetCode，这种提交接口而不是整个程序的方式还是第一次尝试。
当然刚开始也踩了许多坑，比如全局变量的使用。
看了官方文档才发现，实际测试时，同一个全局变量是会被多个实例反复调用的。
因此全局变量必须每次都初始化，根据文档的提醒最好的方式是不要使用全局变量。