Medium

题目描述

给你一个正整数数组 nums。

你需要选择 nums 的一个子集，该子集满足以下条件：

你可以将选中的元素放在一个下标从 0 开始的数组中，使其遵循以下模式：[x, x², x⁴, ..., x^(k/2), x^k, x^(k/2), ..., x⁴, x², 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]，这遵循模式且 2² == 4。因此答案是 3。

示例 2：

输入：nums = [1,3,2,4]
输出：1
解释：我们可以选择子集 {1}，可以将其放在数组中作为 [1]，这遵循模式。因此答案是 1。注意我们也可以选择子集 {2}、{3} 或 {4}，可能有多个子集提供相同的答案。

约束：

  • 2 <= nums.length <= 10⁵
  • 1 <= nums[i] <= 10⁹

解题思路

解题思路

这道题要求我们找到一个满足特定模式的最大子集。模式是 [x, x², x⁴, ..., x^k, ..., x⁴, x², x]，即以某个数为起点，按照平方递增到最大值，然后对称递减。

核心观察：

  1. 对于数字 1，我们可以选择任意奇数个（因为 1 的任何次幂都是 1）
  2. 对于其他数字 x > 1，我们需要找到从 x 开始的最长平方序列
  3. 由于指数增长很快（x, x², x⁴, x⁸…），序列长度不会很大

解题步骤：

  1. 统计每个数字的出现次数
  2. 特殊处理数字 1：如果出现次数为奇数，答案至少是出现次数；如果是偶数，答案至少是出现次数-1
  3. 对于每个大于 1 的数字，尝试构建以它为起点的平方序列
  4. 对于每个序列，计算能构成的最大回文长度

关键点：

  • 序列的长度受限于数字范围，最多不超过 log(log(10⁹)) ≈ 6
  • 对于序列 [x, x², x⁴, …, x^(2k)]，如果每个数字都有足够数量，回文长度为 2k+1
  • 需要检查序列中每个数字是否有足够的出现次数（除了中间元素需要1个，其他都需要2个）

代码实现

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        
        int maxLen = 1;
        
        // 特殊处理数字1
        if (count.count(1)) {
            maxLen = count[1] % 2 == 1 ? count[1] : count[1] - 1;
        }
        
        // 处理其他数字
        for (auto& [num, cnt] : count) {
            if (num == 1) continue;
            
            vector<long long> sequence;
            long long curr = num;
            
            // 构建平方序列
            while (curr <= 1e9 && count.count(curr)) {
                sequence.push_back(curr);
                if (curr > 1e4) break; // 避免溢出
                curr = curr * curr;
            }
            
            // 计算最大回文长度
            int len = 1;
            for (int i = 0; i < sequence.size(); i++) {
                bool canExtend = true;
                for (int j = 0; j <= i; j++) {
                    int needed = (j == i) ? 1 : 2;
                    if (count[sequence[j]] < needed) {
                        canExtend = false;
                        break;
                    }
                }
                if (canExtend) {
                    len = 2 * i + 1;
                }
            }
            
            maxLen = max(maxLen, len);
        }
        
        return maxLen;
    }
};

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        from collections import Counter
        
        count = Counter(nums)
        max_len = 1
        
        # 特殊处理数字1
        if 1 in count:
            max_len = count[1] if count[1] % 2 == 1 else count[1] - 1
        
        # 处理其他数字
        for num in count:
            if num == 1:
                continue
                
            sequence = []
            curr = num
            
            # 构建平方序列
            while curr <= 10**9 and curr in count:
                sequence.append(curr)
                if curr > 10**4:  # 避免溢出
                    break
                curr = curr * curr
            
            # 计算最大回文长度
            length = 1
            for i in range(len(sequence)):
                can_extend = True
                for j in range(i + 1):
                    needed = 1 if j == i else 2
                    if count[sequence[j]] < needed:
                        can_extend = False
                        break
                
                if can_extend:
                    length = 2 * i + 1
            
            max_len = max(max_len, length)
        
        return max_len

public class Solution {
    public int MaximumLength(int[] nums) {
        var count = new Dictionary<int, int>();
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }
        
        int maxLen = 1;
        
        // 特殊处理数字1
        if (count.ContainsKey(1)) {
            maxLen = count[1] % 2 == 1 ? count[1] : count[1] - 1;
        }
        
        // 处理其他数字
        foreach (var kvp in count) {
            int num = kvp.Key;
            if (num == 1) continue;
            
            var sequence = new List<long>();
            long curr = num;
            
            // 构建平方序列
            while (curr <= 1e9 && count.ContainsKey((int)curr)) {
                sequence.Add(curr);
                if (curr > 1e4) break; // 避免溢出
                curr = curr * curr;
            }
            
            // 计算最大回文长度
            int len = 1;
            for (int i = 0; i < sequence.Count; i++) {
                bool canExtend = true;
                for (int j = 0; j <= i; j++) {
                    int needed = (j == i) ? 1 : 2;
                    if (count[(int)sequence[j]] < needed) {
                        canExtend = false;
                        break;
                    }
                }
                if (canExtend) {
                    len = 2 * i + 1;
                }
            }
            
            maxLen = Math.Max(maxLen, len);
        }
        
        return maxLen;
    }
}

var maximumLength = function(nums) {
    const count = new Map();
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    let maxLen = 1;
    
    // Handle the special case of 1
    if (count.has(1)) {
        const ones = count.get(1);
        maxLen = Math.max(maxLen, ones % 2 === 1 ? ones : ones - 1);
    }
    
    // For each number, try to build the longest chain
    for (const [num, freq] of count) {
        if (num === 1) continue;
        
        let current = num;
        let length = 0;
        
        // Build the ascending part of the pattern
        while (count.has(current)) {
            const currentCount = count.get(current);
            if (currentCount < 2 && length > 0) {
                // Need at least 2 for middle elements (except the peak)
                break;
            }
            length++;
            current = current * current;
            if (current > 10**9) break; // Prevent overflow
        }
        
        // The pattern is [x, x^2, x^4, ..., x^k, ..., x^4, x^2, x]
        // So we need 2*length - 1 elements total
        if (length > 0) {
            maxLen = Math.max(maxLen, 2 * length - 1);
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n + k × log(log(max_val)))
空间复杂度O(n)

说明：

  • n 是数组长度，k 是不同数字的个数
  • 对于每个数字，构建平方序列的长度最多是 log(log(10⁹)) ≈ 6
  • 空间复杂度主要用于存储数字计数的哈希表

相关题目