LeetCode 805: Split Array With Same Average

发表于 | | 阅读次数:
字数统计: 857 | 阅读时长 ≈ 3

题目链接

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%