特殊阵列II

3152。特殊阵列II

难度：中等

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

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

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

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

示例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都是奇数。所以这个问题的答案是假的。
子数组是[1,6]。只有一对：(1,6)，它包含具有不同奇偶性的数字。所以这个问题的答案是正确的。

约束：

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

提示：

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

解决方案：

我们需要确定 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中文网其他相关文章！