LeetCode 题解工作台
子集中元素的最大数量
给你一个 正整数 数组 nums 。 你需要从数组中选出一个满足下述条件的 子集 ： 你可以将选中的元素放置在一个下标从 0 开始的数组中，并使其遵循以下模式： [x, x 2 , x 4 , ..., x k/2 , x k , x k/2 , ..., x 4 , x 2 , x] （ 注意 ，…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们用一个哈希表 记录数组 中每个元素出现的次数。对于每个元素 ，我们可以将其不断平方，直到其值在哈希表 中的出现次数小于 为止。此时，我们判断 在哈希表 中的出现次数是否为 ，如果是则说明 仍然可以被选入子集中，否则我们需要从子集中删除一个元素，确保子集个数为奇数。然后我们更新答案。继续枚举下一个元素。 注意我们需要特殊处理 $x = 1$ 的情况。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个 正整数 数组 nums 。
你需要从数组中选出一个满足下述条件的子集：
- 你可以将选中的元素放置在一个下标从 0 开始的数组中，并使其遵循以下模式：
[x, x2, x4, ..., xk/2, xk, xk/2, ..., x4, x2, x]（注意，k可以是任何 非负 的 2 的幂）。例如，[2, 4, 16, 4, 2]和[3, 9, 3]都符合这一模式，而[2, 4, 8, 4, 2]则不符合。
返回满足这些条件的子集中，元素数量的 最大值 。
示例 1：
输入：nums = [5,4,1,2,2]
输出：3
解释：选择子集 {4,2,2} ，将其放在数组 [2,4,2] 中，它遵循该模式，且 22 == 4 。因此答案是 3 。
示例 2：
输入：nums = [1,3,2,4]
输出：1
解释：选择子集 {1}，将其放在数组 [1] 中，它遵循该模式。因此答案是 1 。注意我们也可以选择子集 {2} 、{4} 或 {3} ，可能存在多个子集都能得到相同的答案。
提示：
2 <= nums.length <= 1051 <= nums[i] <= 109
解题思路
方法一：哈希表 + 枚举
我们用一个哈希表 记录数组 中每个元素出现的次数。对于每个元素 ，我们可以将其不断平方，直到其值在哈希表 中的出现次数小于 为止。此时，我们判断 在哈希表 中的出现次数是否为 ，如果是则说明 仍然可以被选入子集中，否则我们需要从子集中删除一个元素，确保子集个数为奇数。然后我们更新答案。继续枚举下一个元素。
注意我们需要特殊处理 的情况。
时间复杂度 ，空间复杂度 。其中 和 分别是数组 的长度和数组 中的最大值。
class Solution:
def maximumLength(self, nums: List[int]) -> int:
cnt = Counter(nums)
ans = cnt[1] - (cnt[1] % 2 ^ 1)
del cnt[1]
for x in cnt:
t = 0
while cnt[x] > 1:
x = x * x
t += 2
t += 1 if cnt[x] else -1
ans = max(ans, t)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Evaluates your ability to implement efficient array scanning techniques.
- question_mark
Assesses your understanding of hash table usage for fast lookups.
- question_mark
Tests your ability to maximize a subset size by iterating over arrays efficiently.
常见陷阱
外企场景- error
Not considering edge cases where no valid subset is found.
- error
Inefficiently handling hash table lookups, causing slow performance.
- error
Overlooking the requirement to track the largest subset during the array scan.
进阶变体
外企场景- arrow_right_alt
You could be asked to implement the same solution using different data structures like sets or arrays.
- arrow_right_alt
The problem might require you to optimize for time or space complexity.
- arrow_right_alt
You could encounter variations that involve different subset conditions or constraints.