2501. 数组中最长的方波
题目描述
给你一个整数数组 nums
。如果 nums
的子序列满足下述条件,则认为该子序列是一个 方波 :
- 子序列的长度至少为
2
,并且 - 将子序列从小到大排序 之后 ,除第一个元素外,每个元素都是前一个元素的 平方 。
返回 nums
中 最长方波 的长度,如果不存在 方波 则返回 -1
。
子序列 也是一个数组,可以由另一个数组删除一些或不删除元素且不改变剩余元素的顺序得到。
示例 1 :
输入:nums = [4,3,6,16,8,2] 输出:3 解释:选出子序列 [4,16,2] 。排序后,得到 [2,4,16] 。 - 4 = 2 * 2. - 16 = 4 * 4. 因此,[4,16,2] 是一个方波. 可以证明长度为 4 的子序列都不是方波。
示例 2 :
输入:nums = [2,3,5,6,7] 输出:-1 解释:nums 不存在方波,所以返回 -1 。
提示:
2 <= nums.length <= 105
2 <= nums[i] <= 105
解法
方法一:哈希表 + 枚举
我们先用哈希表记录数组中的所有元素,然后枚举数组中的每个元素作为子序列的第一个元素,将该元素不断平方,并判断平方后的结果是否在哈希表中,如果在,则将平方后的结果作为下一个元素,继续判断,直到平方后的结果不在哈希表中,此时判断子序列的长度是否大于 $1$,如果是,则更新答案。
时间复杂度 $O(n \times \log \log M)$,空间复杂度 $O(n)$。其中 $n$ 为数组 nums
的长度,而 $M$ 为数组 nums
中的最大元素。
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
方法二:记忆化搜索
与方法一类似,我们先用哈希表记录数组中的所有元素。然后设计一个函数 $dfs(x)$,表示以 $x$ 为第一个元素的方波的长度。那么答案就是 $max(dfs(x))$,其中 $x$ 为数组 nums
中的元素。
函数 $dfs(x)$ 的计算过程如下:
- 如果 $x$ 不在哈希表中,则返回 $0$。
- 否则,返回 $1 + dfs(x^2)$。
过程中我们可以使用记忆化搜索,即使用哈希表记录函数 $dfs(x)$ 的值,避免重复计算。
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为数组 nums
的长度。
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|