题目描述
给你一个 正整数 数组 nums
。
你需要从数组中选出一个满足下述条件的子集:
- 你可以将选中的元素放置在一个下标从 0 开始的数组中,并使其遵循以下模式:
[x, x^2, x^4, ..., x^{k/2}, x^k, x^{k/2}, ..., x^4, x^2, x]
(注意,k
可以是任何 非负 的2
的幂)。例如,[2, 4, 16, 4, 2]
和[3, 9, 3]
都符合这一模式,而[2, 4, 8, 4, 2]
则不符合。
返回满足这些条件的子集中,元素数量的 最大值。
样例
输入:nums = [5,4,1,2,2]
输出:3
解释:选择子集 {4,2,2},将其放在数组 [2,4,2] 中,它遵循该模式,且 2^2 == 4。因此答案是 3。
输入:nums = [1,3,2,4]
输出:1
解释:选择子集 {1},将其放在数组 [1] 中,它遵循该模式。因此答案是 1。
注意我们也可以选择子集 {2} 、{4} 或 {3},可能存在多个子集都能得到相同的答案。
限制
2 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
算法
(枚举,哈希表) $O(n \log \log m)$
- 使用哈希表存储每个数字的出现次数。
- 枚举每个数字作为 $x$、$x^2$、$x^4$ 等,判定是否存在合法的序列。
时间复杂度
- 预处理哈希表的时间复杂度为 $O(n)$。
- 对于每个数字,最多判定 $O(\log \log m)$ 次,这里 $m$ 是最大可能的数字。
- 故总时间复杂度为 $O(n \log \log m)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表。
C++ 代码
#define LL long long
class Solution {
public:
int maximumLength(vector<int>& nums) {
unordered_map<LL, int> seen;
for (int x : nums)
++seen[x];
int ans = 1;
if (seen.count(1)) {
int one = seen[1];
ans = one - (one % 2 == 0);
}
for (const auto &[k, v] : seen){
if (k == 1)
continue;
LL x = k;
int cnt = v, tot = 0;
while (cnt >= 2) {
x *= x;
cnt = seen.count(x) ? seen[x] : 0;
tot += 2;
}
ans = max(ans, tot + (seen.count(x) ? 1 : -1));
}
return ans;
}
};