Skip to content

Latest commit

 

History

History
152 lines (109 loc) · 5.97 KB

805.split-array-with-same-average.md

File metadata and controls

152 lines (109 loc) · 5.97 KB
Raw

题目地址(805. 数组的均值分割)

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].

前置知识

公司

  • 暂无

思路

实际上分出的两个列表 B 和 C 的均值都等于列表 A 的均值，这是本题的入手点。以下是证明：

sum(B) * (N - K) = sum(C) * K
sum(B) * N = (sum(B) + sum(C)) * K
sum(B) / K = (sum(B) + sum(C)) / N
sum(B) / K = sum(A) / N

因此我们可以枚举所有的 A 的大小 i，相应地 B 的大小就是 n - i，其中 n 为数组 A 的大小。而由于两个列表 B 和 C 的均值都等于列表 A 的均值。因此可以提前计算出 A 的均值 avg，那么 A 的总和其实就是 i _ avg ，我们使用回溯找到一个和为 i _ avg 的组合，即可返回 true，否则返回 false。

核心代码：

def splitArraySameAverage(self, A: List[int]) -> bool:
        n = len(A)
        avg = sum(A) / n

        for i in range(1, n // 2 + 1):
            for combination in combinations(A, i):
                if abs(sum(combination) - avg * i) < 1e-6:
                    return True
        return False

上面代码由于回溯里面嵌套了 sum，因此时间复杂度为回溯的时间复杂度 * sum 的时间复杂度，因此总的时间复杂度在最坏的情况下是 $n * 2^n$。

上面的代码思路上可行，但却有很多可以优化的地方。至少我们可以不用计算出来所有的组合之后再求和，而是直接计算所有的和的组合，这种算法的时间复杂度为 $2^n$。

核心代码：

def splitArraySameAverage(self, A: List[int]) -> bool:
        n = len(A)
        avg = sum(A) / n

        for i in range(1, n // 2 + 1):
            for s in combinationSum(A, i):
                if abs(s - avg * i) < 1e-6:
                    return True
        return False

但是遗憾的是，这仍然不足以通过所有的测试用例。接下来，我们可以通过剪枝的手段来达到 AC 的目的。 很多回溯的题目都是基于剪枝来完成的。剪枝是回溯问题的核心考点。

对于这道题来说，我们可以剪枝的点有两个：

  • 剪枝一：对于一个数组 [1,1,3]，任选其中两项，其组合有 3 种。分别是 (1,1), (1,3) 和 (1,3)。实际上，我们可以将两个 (1,3) 看成一样的（部分题目不能看成一样的，但本题可以），如果能将生成同样的组合剪枝掉就好了。我们可以排序的方式进行剪枝，具体参考 40. 组合总和 II
  • 剪枝二：由于每个数字都是整数，那么其和一定也是整数，因此如果和是小数，那么其一定不可能，可以剪枝。

关键点

  • 回溯解题模板
  • 两个剪枝

代码

  • 语言支持：Python3

Python3 Code:

class Solution:
    def combinationSum(self, candidates: List[int], count: int) -> List[List[int]]:
        size = len(candidates)
        if size == 0:
            return []
 
        # 还是先排序，主要是方便去重
        candidates.sort()
 
        ans = []
        self._find_path(candidates, ans, 0, count, 0, size)
        return ans
 
    def _find_path(self, candidates, ans, path_sum, count, begin, size):
        if count == 0:
            ans.append(path_sum)
            return
        else:
            for i in range(begin, size):
                # 剪枝一。 注意这里的 i > begin 这个条件
                if i > begin and candidates[i] == candidates[i - 1]:
                    continue
                self._find_path(candidates, ans, path_sum + candidates[i], count - 1, i + 1, size)
 
    def splitArraySameAverage(self, A: List[int]) -> bool:
        n = len(A)
        avg = sum(A) / n
 
        for i in range(1, n // 2 + 1):
            # 剪枝二
            if abs(i * avg - int(i * avg)) > 1e-6:
                continue
            for s in self.combinationSum(A, i):
                if abs(s - avg * i) < 1e-6:
                    return True
        return False

复杂度分析

令 n 为数组长度。

  • 时间复杂度：$O(2^n)$
  • 空间复杂度：$O(n)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。