LeetCode 解題筆記：3020. Find the Maximum Number of Elements in Subset

作者：王一哲
日期：2026年6月27日


LeetCode 題目連結：3020. Find the Maximum Number of Elements in Subset

解題想法

中等難度題。由於題目要從陣列 $nums$ 之中取最多個數字，數字符合 $x, x^2, x^4, ..., x^{n/2}, x^x, x^{n/2}, ..., x^4, x^2, x$ 的關係，因此解題時要先用字典計數，計算各數字的數量。但是題目的數字有點大，如果用 C++ 解題時，key 值需要用 long long 格式，用 int 會溢位。答案 $ans$ 預設為 $1$，因為至少可以取 $1$ 個數字。接下來先處理全部都取 $1$ 的狀況，如果 $1$ 的數量為 $ones$，長度需要取奇數，更新 $ans$。最後依序從計中數器 $cnt$ 之中取出 key 值 $x$，跳過已經檢查過的 $x = 1$；假設 $sq = \sqrt{x}$，如果 $sq$ 在 $cnt$ 之中而且 $cnt[sq] \geq 2$，代表 $x$ 包含在從 $sq$ 開始往上檢查的過程中，可以跳過，稍微節省一點時間。最後用一個 while 迴圈，如果 $cnt[x] \geq 2$ 而且 $x*x$ 在 $cnt$ 之中就繼續執行，並將長度 $length$ 加 1。結束 while 迴圈之後，更新 $ans$，取 $ans$ 及 $length * 2 + 1$ 較大者。

Python 程式碼

Runtime: 87 ms, beats 98.43%. Memory: 31.53 MB, beats 66.93%.

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        cnt = Counter(nums)  # 每個數字的數量
        ans = 0  # 答案
        # --- 先處理全部都是 1 的特例 ---
        if 1 in cnt:  # 如果 cnt 之中有 1，數量取奇數
            ans = max(ans, cnt[1] - (cnt[1] % 2 == 0))
        # --- 一般狀況 ---
        for x in cnt.keys():
            # 跳過已經檢查過的 1
            if x == 1: continue
            # 如果 isqrt(x) 也在 cnt 之中，x 會包含在從 isqrt(x) 開始的檢查過程中，可以跳過
            sq = isqrt(x)
            if sq > 1 and sq in cnt and cnt[sq] >= 2: continue
            # 從 x 開始往上檢查至 cnt[x] 數量小於 2 或 x*x 不在 cnt 之中或
            length = 0
            while cnt[x] >= 2 and x*x in cnt:
                length += 1
                x *= x
            ans = max(ans, length * 2 + 1)
        return ans

C++ 程式碼

Runtime: 61 ms, beats 84.57%. Memory: 122.86 MB, beats 30.29%.

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        unordered_map<long long, int> cnt;  // 計數器
        for(long long num : nums) cnt[num]++;
        /* 先處理全部都是 1 的特例 */
        int ans = 1;
        if (cnt.count(1) == 1) {
            ans = max(ans, cnt[1] - (cnt[1] % 2 == 0));  // 答案
        }
        /* 一般狀況 */
        for(auto it : cnt) {
            long long x = it.first;
            // 跳過 1，已經處理過
            if (x == 1) continue;
            // sq = (long)sqrt(x)，如果 sq > 1 而且 cnt[sq] >= 2，x 包含在從 sq 開始的檢查之中，跳過
            long long sq = round(sqrt(x));
            if (sq*sq == x && cnt.count(sq) == 1 && cnt[sq] >= 2) continue;
            int length = 0;
            long long curr = x;
            while(cnt[curr] >= 2 && cnt.count(curr * curr) == 1) {
                length++;
                curr *= curr;
            }
            ans = max(ans, length * 2 + 1);
        }
        return ans;
        
    }
};