LeetCode每日一题——805. 数组的均值分割

简介: 给定你一个整数数组 nums我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中,使得 A 数组和 B 数组不为空,并且 average(A) == average(B) 。

题目

给定你一个整数数组 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] <= 104

思路

折半搜索:

这里仅给出大致思路,详细折半查找的学习见官方题解官方题解

1.先遍历 A 的前半部分 B=A[:n//2],得到所有子集和的集合 S

2.如果 S 中没有 0,再遍历 A 的后半部分 C=A[n//2:],得到所有子集和的集合 S2

3.如果 S2 中也没有 0,那遍历 S2 中 的 x,判断 -x 是否在 S 中即可。

注意不能选取整个 A,所以不考虑 x=sum© 的情况。证明:

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

题解

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
目录
相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
38 0
|
3月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
3月前
|
存储 Java API
LeetCode------合并两个有序数组(4)【数组】
这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
LeetCode------合并两个有序数组(4)【数组】
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
114 2
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 03. 数组中重复的数字
解决剑指Offer题目 "数组中重复的数字" 的Python实现方法,通过使用字典来记录数组中每个数字的出现次数,快速找出重复的数字。
39 1
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
3月前
|
前端开发
LeetCode------移动零(5)【数组】
这篇文章介绍了LeetCode上的"移动零"问题,提出了一种使用双指针的原地操作解法,该方法首先将非零元素移动到数组前端并保持相对顺序,然后填充后续位置为零,以达到题目要求。
|
1月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
19 4
|
1月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
19 0
Leetcode第三十三题(搜索旋转排序数组)
|
1月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
58 0
下一篇
无影云桌面