搜索

首页 >后端开发 >php教程 >特殊阵列II

特殊阵列II

Linda Hamilton
Linda Hamilton原创
2024-12-15 06:45:10257浏览

Special Array II

3152。特殊阵列II

难度：中等

主题：数组、二分查找、前缀和

如果数组的每对相邻元素都包含两个具有不同奇偶校验的数字，则该数组被视为特殊。

给定一个整数数组和一个 2D 整数矩阵查询，其中对于 requests[i] = [fromi, toi]，你的任务是检查子数组1 nums[fromi..toi] 是否特殊。

返回布尔值数组，如果 nums[fromi..toi] 特殊.

示例1：

  • 输入： nums = [3,4,1,2,6]，查询 = [[0,4]]
  • 输出： [false]
  • 解释：子数组是[3,4,1,2,6]。 2 和 6 都是偶数。

示例2：

  • 输入： nums = [4,3,1,6]，queries = [[0,2],[2,3]]
  • 输出： [假，真]
  • 说明：
    子数组是[4,3,1]。 3和1都是奇数。所以这个问题的答案是假的。
    2. 子数组是[1,6]。只有一对：(1,6)，它包含具有不同奇偶性的数字。所以这个问题的答案是正确的。

约束：

    1 5 1 5 1 5 查询[i].length == 2
    • 0

提示：

    尝试将数组分割成一些不相交的连续特殊子数组。
    2. 对于每个查询，检查该查询的第一个和最后一个元素是否位于同一子数组中。

解决方案：

我们需要确定 nums 的子数组是否“特殊”，即子数组中的每对相邻元素必须具有不同的奇偶性（一个必须是奇数，另一个必须是偶数）。

方法：

  1. 识别奇偶校验跃迁： 我们可以对数组进行预处理来标记奇偶校验发生变化的位置。例如：
      0代表偶数。
      • 1代表奇数。
这个想法是识别相邻元素具有不同奇偶性的所有位置。这将帮助我们通过检查查询中的位置是否属于同一“特殊”块来有效地确定子数组是否特殊。

  1. 预处理： 创建一个二进制数组 parity_change，其中如果相邻元素具有不同的奇偶校验，则每个元素为 1，否则为 0。例如：

    • 如果 nums[i] 和 nums[i 1] 奇偶校验不同，则设置 parity_change[i] = 1，否则为 0。

  2. 前缀和数组：
    构造一个前缀和数组 prefix_sum，其中索引 i 处的每个条目表示到该索引的奇偶校验转换的累积数量。这有助于快速检查子数组中的所有对是否具有不同的奇偶校验。

  3. 查询处理：
    对于每个查询 [from, to]，检查 [from, to-1] 范围内是否存在奇偶校验不变的位置。这可以通过检查前缀总和值的差异来完成： prefix_sum[to] - prefix_sum[from].

让我们用 PHP 实现这个解决方案：3152。特殊阵列II

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

// Example usage
$nums1 = [3,4,1,2,6];
$queries1 = [[0, 4]];
print_r(specialArray($nums1, $queries1)); // [false]

$nums2 = [4,3,1,6];
$queries2 = [[0, 2], [2, 3]];
print_r(specialArray($nums2, $queries2)); // [false, true]
?>

解释：

  1. 预处理奇偶校验转换：
    如果元素 nums[i] 和 nums[i 1] 具有不同的奇偶校验，我们计算 parity_change[i] = 1。否则，我们将其设置为 0。

  2. 前缀和数组：
    prefix_sum[i] 存储从数组开头到索引 i 的奇偶校验转换的累积计数。这使我们能够使用以下公式计算在恒定时间内任何子数组 [from, to] 中发生的转换次数：

   $transition_count = $prefix_sum[$to] - $prefix_sum[$from];
  1. 查询评估： 对于每个查询，如果转换次数等于子数组的长度减 1，则该子数组是特殊的，我们返回 true。否则，我们返回 false。

时间复杂度：

  • 预处理奇偶校验转换需要 O(n)。
  • 构造前缀和数组需要 O(n)。
  • 使用前缀和数组可以在 O(1) 内回答每个查询。
  • 因此，总时间复杂度为 O(n q)，其中 n 是数组长度，q 是查询次数。

该解决方案通过优化的方法有效地处理了问题约束。

联系链接

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

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

  • 领英
  • GitHub

  1. 子数组 子数组 是数组中连续的元素序列。 ↩

以上是特殊阵列II的详细内容。更多信息请关注PHP中文网其他相关文章！

php Integer Array if count for try using Length number this position input github idea Other
声明：
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn
上一篇：How to Safely Set Nested Array Values Using a String Path in PHP?下一篇：How Can I Recursively Walk a Directory and Get All File and Folder Paths Using PHP?

相关文章

查看更多