M3020.子集中元素的最大数量

hash table, https://leetcode.cn/problems/find-the-maximum-number-of-elements-in-subset/

给你一个 正整数 数组 nums 。

你需要从数组中选出一个满足下述条件的子集：

你可以将选中的元素放置在一个下标从 0 开始的数组中，并使其遵循以下模式：[x, x^2, x^4, ..., x^{k/2}, x^k, x^{k/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] 中，它遵循该模式，且 2^2 == 4 。因此答案是 3 。

示例 2：

输入：nums = [1,3,2,4]
输出：1
解释：选择子集 {1}，将其放在数组 [1] 中，它遵循该模式。因此答案是 1 。注意我们也可以选择子集 {2} 、{4} 或 {3} ，可能存在多个子集都能得到相同的答案。

提示：

2 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

这个问题要求我们在数组中找到一个特定模式的子集，其形式为 [x, x^2, x^4, ..., x^k, ..., x^4, x^2, x]。

核心逻辑分析：

模式特征：
- 除了“中心峰值”元素 $x^{k}$ 以外，其余每个元素（ $x, x^{2}, \dots$ ）都必须在子集中出现至少两次（因为是对称的）。
- 中心峰值元素 $x^{k}$ 至少出现一次。
- 模式的长度始终是奇数。
- 如果起始元素 $x = 1$ ，由于 $1$ 的任何次方都是 $1$ ，规律变为 [1, 1, 1, ..., 1]。题目要求遵循该模式，对于 $1$ 来说，只要选择奇数个 $1$ ，就能满足对称的平方关系。
特殊情况 $x = 1$ ：
- 如果我们有 $c$ 个 $1$ ，那么能组成的最长子集长度是 $c$ （如果 $c$ 是奇数）或者 $c - 1$ （如果 $c$ 是偶数）。
- 总结：max_len = c if c % 2 != 0 else c - 1。
一般情况 $x > 1$ ：
- 遍历数组中每一个存在的数字作为起始 $x$ 。
- 尝试不断平方： $x \to x^{2} \to x^{4} \to \dots$
- 如果当前数字 $v$ 的出现次数 $\geq 2$ ，我们可以把它作为模式中的一对（左右各一个），然后继续检查 $v^{2}$ 。
- 如果当前数字 $v$ 的出现次数 $= 1$ ，它只能作为“中心峰值”，此时序列停止。
- 如果当前数字 $v$ 的出现次数 $= 0$ ，说明前一个数字虽然有 $\geq 2$ 个，但其中一个必须作为“中心峰值”，序列停止。

Python 代码实现：

python

from collections import Counter
from typing import List

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        # 1. 统计每个数字出现的频率
        count = Counter(nums)
        ans = 0
        
        # 2. 处理 x = 1 的特殊情况
        if 1 in count:
            c = count[1]
            # 1 构成的子集长度必须是奇数
            ans = c if c % 2 != 0 else c - 1
            
        # 3. 处理 x > 1 的情况
        # 遍历统计字典中的键（即去重后的数字）
        for x in count:
            if x == 1:
                continue
            
            curr_len = 0
            curr_val = x
            
            # 只要当前值出现次数 >= 2，就可以往两边放，继续寻找平方值
            while curr_val in count and count[curr_val] >= 2:
                curr_len += 2
                curr_val = curr_val * curr_val
            
            # 循环结束时，curr_val 可能是：
            # A. 出现次数为 1：它可以作为中心峰值
            # B. 出现次数为 0：它不存在，上一个数字（出现 >=2 次的那个）必须扣掉一个来当峰值
            if curr_val in count and count[curr_val] >= 1:
                curr_len += 1
            else:
                curr_len -= 1
            
            ans = max(ans, curr_len)
            
        return ans

复杂度分析：

时间复杂度： $O (N)$ 。
- 统计频率需要 $O (N)$ 。
- 遍历唯一元素。对于每个 $x \geq 2$ ，其平方增长极快（ $x^{2}, x^{4}, x^{8}, x^{16}, x^{32}$ ）。因为题目限制 $n u m s [i] \leq 10^{9}$ ，且 $2^{32} > 10^{9}$ ，所以 while 循环对每个起始值最多运行 5-6 次。
- 因此，总时间复杂度与数组长度 $N$ 呈线性关系。
空间复杂度： $O (N)$ 。主要开销是存储频率的哈希表（Counter）。

示例运行：

对于 nums = [5, 4, 1, 2, 2]：

count = {5:1, 4:1, 1:1, 2:2}
处理 1: ans = 1。
处理 2: count[2]=2 (len=2), 下一个是 4。count[4]=1 (len=2+1=3)。ans = 3。
处理 4: count[4]=1 (len=1)。ans 保持 3。
处理 5: count[5]=1 (len=1)。ans 保持 3。最终返回 3。

M3020.子集中元素的最大数量 ​

M3020.子集中元素的最大数量