Every day a Leetcode
题目来源:3020. 子集中元素的最大数量
解法1:哈希 + 枚举
用一个哈希表统计数组 nums 中的元素及其出现次数。
暴力枚举数组中的数,作为 x,然后不断看 x2,x4,⋯ 在数组中的个数。直到个数不足 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)。