子集中元素的最大数量

You are given an array of positive integers nums.

You need to select a subset of nums which satisfies the following condition:

• You can place the selected elements in a 0-indexed array such that it follows the pattern: [x, x2, x4, ..., xk/2, xk, xk/2, ..., x4, x2, x] (Note that k can be be any non-negative power of 2). For example, [2, 4, 16, 4, 2] and [3, 9, 3] follow the pattern while [2, 4, 8, 4, 2] does not.

Return the maximum number of elements in a subset that satisfies these conditions.

 

Example 1:

Input: nums = [5,4,1,2,2]
Output: 3
Explanation: We can select the subset {4,2,2}, which can be placed in the array as [2,4,2] which follows the pattern and 22 == 4. Hence the answer is 3.

Example 2:

Input: nums = [1,3,2,4]
Output: 1
Explanation: We can select the subset {1}, which can be placed in the array as [1] which follows the pattern. Hence the answer is 1. Note that we could have also selected the subsets {2}, {3}, or {4}, there may be multiple subsets which provide the same answer. 

 

Constraints:

• 2 <= nums.length <= 105
• 1 <= nums[i] <= 109

/*
题目思路：
1. 使用流处理，将数组排序。
2. 使用动态规划计算满足条件的最大子集长度。
3. dp[i] 表示以第 i 个数为结尾的满足条件的子集的最大长度。
4. 对于每个数，找到之前的数，如果其平方是当前数，则更新 dp 值。
5. 最终返回 dp 数组中的最大值。
*/

import java.util.*;
import java.util.stream.*;

public class Solution {
    public int longestSubset(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int[] sortedNums = Arrays.stream(nums).sorted().toArray();
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (sortedNums[i] == sortedNums[j] * sortedNums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}

题解的核心思路是构建一个频率计数的哈希表，然后遍历每个数，尝试构建符合题意的数组。对于每个数k，尝试构建以k开始的序列[k, k^2, (k^2)^2, ...]，直到当前的数x不在哈希表中或其计数小于等于1。对于特殊的数字1，由于任何数的0次方都是1，我们需要特别处理，最优的情况是使用所有的1构成[1, 1, ..., 1]，长度为cnt[1]（cnt为1的个数）。对于其他数字，每次迭代尝试计算以当前数字为基础能构成的最长序列的长度，并更新答案。

O(n loglogm)

O(n)