class Solution {
public:
int maximumLength(vector<int>& nums) {
}
};
100206. 子集中元素的最大数量
给你一个 正整数 数组 nums 。
你需要从数组中选出一个满足下述条件的子集：
[x, x2, x4, ..., xk/2, xk, xk/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] 中，它遵循该模式，且 22 == 4 。因此答案是 3 。
示例 2：
输入：nums = [1,3,2,4]
输出：1
解释：选择子集 {1}，将其放在数组 [1] 中，它遵循该模式。因此答案是 1 。注意我们也可以选择子集 {2} 、{4} 或 {3} ，可能存在多个子集都能得到相同的答案。
提示：
2 <= nums.length <= 1051 <= nums[i] <= 109原站题解
golang 解法, 执行用时: 151 ms, 内存消耗: 8.5 MB, 提交时间: 2024-01-28 23:38:30
func maximumLength(nums []int) int {
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
ans := cnt[1] - (cnt[1]%2 ^ 1)
delete(cnt, 1)
for x := range cnt {
res := 0
for ; cnt[x] > 1; x *= x {
res += 2
}
res += cnt[x]
ans = max(ans, res-(res%2^1)) // 保证 res 是奇数
}
return ans
}
java 解法, 执行用时: 52 ms, 内存消耗: 56.7 MB, 提交时间: 2024-01-28 23:38:17
class Solution {
public int maximumLength(int[] nums) {
HashMap<Long, Integer> cnt = new HashMap<>();
for (int x : nums) {
cnt.merge((long) x, 1, Integer::sum);
}
Integer c1 = cnt.remove(1L);
int ans = c1 != null ? c1 - (c1 % 2 ^ 1) : 0;
for (long x : cnt.keySet()) {
int res = 0;
for (; cnt.getOrDefault(x, 0) > 1; x *= x) {
res += 2;
}
ans = Math.max(ans, res + (cnt.containsKey(x) ? 1 : -1)); // 保证 res 是奇数
}
return ans;
}
}
cpp 解法, 执行用时: 210 ms, 内存消耗: 119.5 MB, 提交时间: 2024-01-28 23:38:02
class Solution {
public:
int maximumLength(vector<int> &nums) {
unordered_map<long long, int> cnt;
for (int x : nums) {
cnt[x]++;
}
int ans = cnt[1] - (cnt[1] % 2 ^ 1);
cnt.erase(1);
for (auto &[num, _] : cnt) {
int res = 0;
long long x = num;
for (; cnt.contains(x) && cnt[x] > 1; x *= x) {
res += 2;
}
ans = max(ans, res + (cnt.contains(x) ? 1 : -1)); // 保证 res 是奇数
}
return ans;
}
};
python3 解法, 执行用时: 165 ms, 内存消耗: 28.1 MB, 提交时间: 2024-01-28 23:37:48
class Solution:
def maximumLength(self, nums: List[int]) -> int:
cnt = Counter(nums)
ans = cnt[1] - (cnt[1] % 2 ^ 1)
del cnt[1]
for x in cnt:
res = 0
while cnt[x] > 1:
res += 2
x *= x
ans = max(ans, res + (1 if x in cnt else -1)) # 保证 res 是奇数
return ans