子集中元素的最大数量

难度: Medium

给你一个 正整数 数组 nums 。

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

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

示例 2：

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

提示：

2 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Submission

运行时间: 131 ms

内存: 28.2 MB

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        ans = max(1, cnt[1] - 1 + cnt[1] % 2)
        for k, v in cnt.items():
            if k == 1 or v == 1:
                continue
            i, x = 1, k * k
            while x in cnt:
                i += 2
                if cnt[x] <= 1:
                    break
                x *= x    
            ans = max(ans, i)
        return ans

Explain

题解的核心思路是构建一个频率计数的哈希表，然后遍历每个数，尝试构建符合题意的数组。对于每个数k，尝试构建以k开始的序列[k, k^2, (k^2)^2, ...]，直到当前的数x不在哈希表中或其计数小于等于1。对于特殊的数字1，由于任何数的0次方都是1，我们需要特别处理，最优的情况是使用所有的1构成[1, 1, ..., 1]，长度为cnt[1]（cnt为1的个数）。对于其他数字，每次迭代尝试计算以当前数字为基础能构成的最长序列的长度，并更新答案。

时间复杂度: O(n loglogm)

空间复杂度: O(n)

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        cnt = Counter(nums)  # 计数nums中每个数字的出现次数
        ans = max(1, cnt[1] - 1 + cnt[1] % 2)  # 特殊处理数字1，计算只包含数字1的数组最大长度
        for k, v in cnt.items():
            if k == 1 or v == 1:
                continue  # 如果数字是1或只出现一次则跳过
            i, x = 1, k * k
            while x in cnt:
                i += 2  # 成功构建更长的序列，长度增加2
                if cnt[x] <= 1:
                    break  # 如果当前数字x的计数小于等于1则停止
                x *= x  # 更新x为下一个平方
            ans = max(ans, i)  # 更新答案
        return ans # 返回最终答案

Explore

在构建哈希表时，我使用了Python的`Counter`类，这是`collections`模块中的一个特殊类，用于计数对象中元素的出现次数。当出现重复元素时，`Counter`会自动为每个元素维护一个计数器。因此，每次元素出现时，其对应的计数就会增加，从而有效地记录了每个数字出现的次数。这允许我们在后续的逻辑处理中方便地访问每个数字的频率，以决定如何构建目标序列。

数字1需要特别处理，因为1的任何次幂都等于1，这与其他数字不同。如果按照其他数字的处理方式，即构建形如[k, k^2, (k^2)^2, ...]的序列，对1来说这个序列将会是[1, 1, 1, ...]，实际上没有增长。因此，最优的处理方法是直接计算1出现的次数，构建一个仅包含1的数组，其长度等于1出现的次数。这种方法直接利用了1的这一特性，而不需要进入更复杂的平方序列构建过程。

在处理如`k^2^2`这样的高次幂时，确实存在整数溢出的风险，尤其是在某些编程语言中。在Python中，整数类型是动态的，可以处理非常大的数而不会溢出，但这并不意味着没有性能问题。为了避免在实际应用中处理过大的数字，我的实现在每次计算高次幂时都会检查当前数字是否仍存在于哈希表中以及对应的计数是否大于1。如果这两个条件任何一个不满足，循环将停止。这样，我们可以在实际中限制序列的长度和数值的大小，避免不必要的计算和潜在的性能问题。