LeetCode 805: Split Array With Same Average

题目链接

https://leetcode-cn.com/problems/split-array-with-same-average/

题意

给定的整数数组 A ,我们要将 A数组 中的每个元素移动到 B数组 或者 C数组中。(B数组和C数组在开始的时候都为空)

返回true ,当且仅当在我们的完成这样的移动后,可使得B数组的平均值和C数组的平均值相等,并且B数组和C数组都不为空。

示例:
输入:
[1,2,3,4,5,6,7,8]
输出: true
解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。

注意:

A 数组的长度范围为 [1, 30].
A[i] 的数据范围为 [0, 10000].

题目类型

动态规划

题目分析

没能独立完成的题目,参考了[Leetcode] 805. Split Array With Same Average 解题报告解出。
实质上题目是一个有点像DP但其实又不太DP的暴力题。
题目有几个可以挖掘的特性:

  1. B, C两个序列是等价的,也就是我们只要找出长度不超过n/2的序列就可以了(另一半直接减了得到)
  2. 假设最后分为了两个序列 B, C, 假设序列B的长度为k序列C长一些 (1 <= k <= n/2) ,则我们可得到 total_sum / n = B_sum / k = C_sum / (n - k),则可得到B_sum = total_sum * k / n,由于B_sum一定为整数,因此 total_sum * k % n == 0,一开始我们可以对 total_sum 进行特判,如果 1 <= k <= n/2 的所有 k 都不满足该条件则可以提前返回 false
  3. 如果发现确实有符合条件的k,则用数组 dp[i] 保存长度为 i 的所有序列B的可能和,每个 dp[i] 为一个 unordered_set,加入 A 中某个数 num 的时候可以得到 dp[i] = dp[i] join { for each dp[i - 1] + num},这一步我们可以采用类似背包问题时的方法,长度从大往小枚举就可以保证这次的不会被重复累积进去了(类似背包省掉 n 的那一维空间)
  4. 有了各个长度 i 对应的 set 即 dp[i] 以后,我们只需要检查相应长度 i 是否含有元素 total_sum * i / n 即可,一旦发现存在符合条件的 i,返回 true 即可,否则返回 false

时间复杂度

$O(N ^ 3 * M)$
M为元素的组合数(恶劣情况可达$N ^ 2$)

源代码

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
class Solution {
public:
bool splitArraySameAverage(vector<int>& A) {
int n = A.size(), m = n / 2;
vector<unordered_set<int>>dp(m + 1);
int i;
dp[0].insert(0);
int sum = accumulate(A.begin(), A.end(), 0);
bool isPossible = false;
for (i = 1; i <= m; i++) {
if (sum * i % n == 0) {
isPossible = true;
break;
}
}
if (!isPossible)
return false;
for (int num : A) {
for (i = m; i > 0; --i) {
for (auto t : dp[i - 1]) {
dp[i].insert(t + num);
}
}
}
for (i = 1; i <= m; i++) {
if (sum * i % n == 0 && dp[i].count(sum * i / n))
return true;
}
return false;
}
};

题外话

这道题做完后学会了一些比较有趣的 C++ 赋值法,可能是之前太菜了都没学过:

  • vector 求和可以用 accumulate(A.begin(), A.end(), 0); 最后一位 0 表示偏移量
  • vector 新建并赋初值可以用 vector<int>A = vector<int>({1,2,3,4,5}); 解决
  • map 也可以 map<int>S = map<int>({0}); 要想建空的就直接不要填{}就好了
0%