0805：数组的均值分割（1982 分）

Ian

2017-03-15 约 1008 字预计阅读 3 分钟次阅读

力扣第 805 题

题目

给定你一个整数数组 nums

我们要将 nums 数组中的每个元素移动到 A 数组或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。

如果可以完成则返回true ，否则返回 false 。

注意：对于数组 arr , average(arr) 是 arr 的所有元素的和除以 arr 长度。

示例 1:

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

示例 2:

输入: nums = [3,1]
输出: false

提示:

1 <= nums.length <= 30
0 <= nums[i] <= 10⁴

分析

#1

类似 0416，不过分割条件从和相等变成了平均数相等。

什么情况下两者等价？平均数为 0 的时候。于是有个巧妙的想法：

将 nums 的数都减去平均数得到新数组 A，问题就等价于将 A 分割为和相等的两部分。
注意平均数可能为浮点数，为了精确，可以将 nums 的数都先乘以一个合适的 mul 使得平均数为整数。
转换完成后递推子集和的集合找 0 即可。

注意不能选取整个 A，因此考虑只遍历 A[:-1]，假如没有得到 0，即非真。证明：

假如 A[:-1] 的子集和都不为 0，那么 A[:-1] 的任意真子集 A’ 的和不等于 sum(A[:-1])（因为 A[:-1]-A’ 的和不为 0）
那么 A[-1] 和 A[:-1] 的任意真子集 A’ 的总和不等于 sum(A)=0
因此 A 的任意真子集的和不为 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def splitArraySameAverage(self, nums: List[int]) -> bool:
    n, s = len(nums), sum(nums)
    mul = n//gcd(n, s)
    A = [num*mul-mul*s//n for num in nums]
    res = set()
    for x in A[:-1]:
        res |= {sub+x for sub in res|{0}}
        if 0 in res:
            return True
    return False

592 ms

#2

还可以类似 0416 的状压优化方法，将集合状态压缩为一个数 state，优化递推时间。

这里有个问题是集合中有负数，不能压缩到 state 中。一个巧妙的想法是：

先遍历正数，再遍历负数
那么遇到某个子集和为负数时，必然已经遍历到负数，那么后面不可能变为 0 了，无需保存
所以只维护非负数的集合即可，可以压缩为 state

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def splitArraySameAverage(self, nums: List[int]) -> bool:
    n, s = len(nums), sum(nums)
    mul = n//gcd(n, s)
    A = [num*mul-mul*s//n for num in nums]
    st = 0
    for x in sorted(A[:-1], reverse=True):
        st |= (st|1)<<x if x>=0 else st>>(-x)
        if st & 1:
            return True
    return False

36 ms

*附加

本题还有个经典的优化方法，折半搜索：

先遍历 A 的前半部分 B=A[:n//2]，得到所有子集和的集合 S
如果 S 中没有 0，再遍历 A 的后半部分 C=A[n//2:]，得到所有子集和的集合 S2
如果 S2 中也没有 0，那遍历 S2 中的 x，判断 -x 是否在 S 中即可。

注意不能选取整个 A，所以不考虑 x=sum(C) 的情况。证明：

C 的子集和都不为 0，那么 C 的任意真子集的和不等于 sum(C)
因此 x=sum(C) 必然对应整个 C
B 的子集和都不为 0，那么 B 的任意真子集的和不等于 sum(B)
因此 -x=sum(B) 必然对应整个 B

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


def splitArraySameAverage(self, nums: List[int]) -> bool:
    n, s = len(nums), sum(nums)
    mul = n//gcd(n, s)
    A = [num*mul-mul*s//n for num in nums]
    S = set()
    for x in A[:n//2]:
        S |= {sub+x for sub in S|{0}}
        if 0 in S:
            return True
    S2, rs = set(), sum(A[n//2:])
    for x in A[n//2:]:
        for sub in S2|{0}:
            y = sub+x
            if y != rs and (y==0 or -y in S):
                return True
            S2.add(y)
    return False

64 ms

目录

0805：数组的均值分割（1982 分）

题目

分析

#1

#2

解答

*附加