阵列中最长的方形条纹

2501。数组中最长的方形条纹

难度：中等

主题：数组、哈希表、二分查找、动态规划、排序

给你一个整数数组 nums。 nums 的子序列称为 square streak 如果：

• 子序列的长度至少为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 5
• 2 5

提示：

1. 在约束条件下，最长方形条纹的长度可能为 5。
2. 将 nums 的元素存储在一个集合中，以快速检查它是否存在。

解决方案：

我们需要识别 nums 数组中最长的方形条纹。方形条纹是一个子序列，其中每个后续元素都是前一个元素的平方，并且它的长度必须至少为两个元素。

解决方法如下：

1. 使用集合进行快速查找:

   • 将数字存储在集合中，以快速验证元素的方块是否也在数组中。

2. 迭代数组:

   • 对于数组中的每个数字，尝试从该数字开始构建一条方形条纹。
   • 检查当前数字的平方是否存在于集合中，并继续延长连胜，直到没有进一步的平方匹配。

3. 轨道最大长度:

   • 跟踪遇到的所有可能的方形条纹的最大长度。如果没有找到方形条纹，则返回-1。

4. 优化：

   • 在检查每个元素之前对数组进行排序，以确保按升序检查子序列。这将有助于避免多余的检查。

让我们用 PHP 实现这个解决方案：2501。数组中最长的方形条纹

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function longestSquareStreak($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$nums1 = [4, 3, 6, 16, 8, 2];
echo longestSquareStreak($nums1) . "\n";  // Output: 3

$nums2 = [2, 3, 5, 6, 7];
echo longestSquareStreak($nums2) . "\n";  // Output: -1
?>

解释：

• 排序：对 nums 进行排序确保我们可以按升序检查序列。
• 集合查找：使用 array_flip 为 $numSet 创建一个类似集合的结构，以 $nums 作为键，允许快速存在性检查。
• 循环遍历每个数字：对于nums中的每个num，检查当前数字的平方是否在集合中。如果是，则继续连胜。否则，打破连胜并检查它是否是找到的最长连胜。

复杂性分析

• 时间复杂度: O(n log n) 由于排序，其中 n 是元素数量数字。随后的查找和方形条纹检查是 O(n).
• 空间复杂度：O(n)，主要用于存储集合中的nums。

此解决方案有效地找到最长的方形条纹，如果不存在有效条纹，则返回 -1。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是阵列中最长的方形条纹的详细内容。更多信息请关注PHP中文网其他相关文章！