Every day a Leetcode

题目来源：3020. 子集中元素的最大数量

解法1：哈希 + 枚举

用一个哈希表统计数组 nums 中的元素及其出现次数。

暴力枚举数组中的数，作为 x，然后不断看 x²,x⁴,⋯ 在数组中的个数。直到个数不足 2 个为止，退出循环。

注意模式的正中间的数字只取一个。如果最后 x 有一个，那么个数加一，否则个数减一。

注意特判 x=1 的情况。

代码：

/** @lc app=leetcode.cn id=100206 lang=cpp** [100206] 子集中元素的最大数量*/// @lc code=start
class Solution
{
public:int maximumLength(vector<int> &nums){// 特判if (nums.empty())return 0;unordered_map<long long, int> cnt;for (int &num : nums)cnt[num]++;// 特判 x=1 的情况int ans = cnt[1] - (cnt[1] % 2 == 0);cnt.erase(1);for (auto &[num, _] : cnt){int res = 0;long long x;for (x = num; cnt.contains(x) && cnt[x] > 1; x *= x)res += 2;if (cnt.contains(x))res++;elseres--;ans = max(ans, res);}return ans;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(nloglogU)，其中 n 为数组 nums 的长度，U=max⁡(nums)。

空间复杂度：O(n)。