数组的均值分割

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⁴

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool splitArraySameAverage(vector<int>& nums) { } };

golang 解法, 执行用时: 72 ms, 内存消耗: 12.5 MB, 提交时间: 2022-11-14 09:48:00

func splitArraySameAverage(nums []int) bool {
    sum := 0
    for _, x := range nums {
        sum += x
    }

    n := len(nums)
    m := n / 2
    isPossible := false
    for i := 1; i <= m; i++ {
        if sum*i%n == 0 {
            isPossible = true
            break
        }
    }
    if !isPossible {
        return false
    }

    dp := make([]map[int]bool, m+1)
    for i := range dp {
        dp[i] = map[int]bool{}
    }
    dp[0][0] = true
    for _, num := range nums {
        for i := m; i >= 1; i-- {
            for x := range dp[i-1] {
                curr := x + num
                if curr*n == sum*i {
                    return true
                }
                dp[i][curr] = true
            }
        }
    }
    return false
}

python3 解法, 执行用时: 216 ms, 内存消耗: 39.4 MB, 提交时间: 2022-11-14 09:46:45

class Solution:
    def splitArraySameAverage(self, nums: List[int]) -> bool:
        '''
        dp[i][x] 表示当前已从数组 nums 取出 i 个元素构成的和为 x 的可能性：
        如果 dp[i][x]=true，表示当前已经遍历过的元素中可以取出 i 个元素构成的和为 x；
        如果 dp[i][x]=false，表示当前已经遍历过的元素中不存在取出 i 个元素的和等于 x；
        dp[i+1][x+nums[j]]=dp[i][x]
        '''

        n = len(nums)
        m = n // 2
        s = sum(nums)
        if all(s * i % n for i in range(1, m + 1)):
            return False

        dp = [set() for _ in range(m + 1)]
        dp[0].add(0)
        for num in nums:
            for i in range(m, 0, -1):
                for x in dp[i - 1]:
                    curr = x + num
                    if curr * n == s * i:
                        return True
                    dp[i].add(curr)
        return False

python3 解法, 执行用时: 964 ms, 内存消耗: 18.6 MB, 提交时间: 2022-11-14 09:40:16

class Solution:
    def splitArraySameAverage(self, nums: List[int]) -> bool:
        n = len(nums)
        if n == 1:
            return False
        s = sum(nums)
        for i, v in enumerate(nums):
            nums[i] = v * n - s
        m = n >> 1 #取半
        vis = set()
        for i in range(1, 1 << m):
            t = sum(v for j, v in enumerate(nums[:m]) if i >> j & 1)  # 前半部分每个子数组元素之和
            if t == 0:
                return True
            vis.add(t)
        for i in range(1, 1 << (n - m)):
            t = sum(v for j, v in enumerate(nums[m:]) if i >> j & 1)  # 后半部分每个子数组之和
            if t == 0 or (i != (1 << (n - m)) - 1 and -t in vis):
                return True
        return False

上一题

下一题

详情