3152。特殊陣列II

難度：中等

主題：數(shù)組、二分查找、前綴和

如果數(shù)組的每對(duì)相鄰元素都包含兩個(gè)具有不同奇偶校驗(yàn)的數(shù)字，則該數(shù)組被視為特殊。

給定一個(gè)整數(shù)數(shù)組和一個(gè) 2D 整數(shù)矩陣查詢，其中對(duì)于 requests[i] = [from_i, to_i]，你的任務(wù)是檢查子數(shù)組¹ nums[from_i..to_i] 是否特殊。

返回布爾值數(shù)組，如果 nums[from_i..to_i] 特殊.

示例1：

• 輸入： nums = [3,4,1,2,6]，查詢 = [[0,4]]
• 輸出： [false]
• 解釋：子數(shù)組是[3,4,1,2,6]。 2 和 6 都是偶數(shù)。

示例2：

• 輸入： nums = [4,3,1,6]，queries = [[0,2],[2,3]]
• 輸出： [假，真]
• 說(shuō)明：

子數(shù)組是[4,3,1]。 3和1都是奇數(shù)。所以這個(gè)問(wèn)題的答案是假的。
子數(shù)組是[1,6]。只有一對(duì)：(1,6)，它包含具有不同奇偶性的數(shù)字。所以這個(gè)問(wèn)題的答案是正確的。

約束：

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

提示：

嘗試將數(shù)組分割成一些不相交的連續(xù)特殊子數(shù)組。
對(duì)于每個(gè)查詢，檢查該查詢的第一個(gè)和最后一個(gè)元素是否位于同一子數(shù)組中。

解決方案：

我們需要確定 nums 的子數(shù)組是否“特殊”，即子數(shù)組中的每對(duì)相鄰元素必須具有不同的奇偶性（一個(gè)必須是奇數(shù)，另一個(gè)必須是偶數(shù)）。

方法：

1. 識(shí)別奇偶校驗(yàn)躍遷： 我們可以對(duì)數(shù)組進(jìn)行預(yù)處理來(lái)標(biāo)記奇偶校驗(yàn)發(fā)生變化的位置。例如：
   0代表偶數(shù)。
   1代表奇數(shù)。

這個(gè)想法是識(shí)別相鄰元素具有不同奇偶性的所有位置。這將幫助我們通過(guò)檢查查詢中的位置是否屬于同一“特殊”塊來(lái)有效地確定子數(shù)組是否特殊。

1. 預(yù)處理： 創(chuàng)建一個(gè)二進(jìn)制數(shù)組 parity_change，其中如果相鄰元素具有不同的奇偶校驗(yàn)，則每個(gè)元素為 1，否則為 0。例如：
   

   • 如果 nums[i] 和 nums[i 1] 奇偶校驗(yàn)不同，則設(shè)置 parity_change[i] = 1，否則為 0。

2. 前綴和數(shù)組：
   構(gòu)造一個(gè)前綴和數(shù)組 prefix_sum，其中索引 i 處的每個(gè)條目表示到該索引的奇偶校驗(yàn)轉(zhuǎn)換的累積數(shù)量。這有助于快速檢查子數(shù)組中的所有對(duì)是否具有不同的奇偶校驗(yàn)。

3. 查詢處理：
   對(duì)于每個(gè)查詢 [from, to]，檢查 [from, to-1] 范圍內(nèi)是否存在奇偶校驗(yàn)不變的位置。這可以通過(guò)檢查前綴總和值的差異來(lái)完成： prefix_sum[to] - prefix_sum[from].

讓我們用 PHP 實(shí)現(xiàn)這個(gè)解決方案：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. 預(yù)處理奇偶校驗(yàn)轉(zhuǎn)換：
   如果元素 nums[i] 和 nums[i 1] 具有不同的奇偶校驗(yàn)，我們計(jì)算 parity_change[i] = 1。否則，我們將其設(shè)置為 0。

2. 前綴和數(shù)組：
   prefix_sum[i] 存儲(chǔ)從數(shù)組開(kāi)頭到索引 i 的奇偶校驗(yàn)轉(zhuǎn)換的累積計(jì)數(shù)。這使我們能夠使用以下公式計(jì)算在恒定時(shí)間內(nèi)任何子數(shù)組 [from, to] 中發(fā)生的轉(zhuǎn)換次數(shù)：
   

   $transition_count = $prefix_sum[$to] - $prefix_sum[$from];

1. 查詢?cè)u(píng)估： 對(duì)于每個(gè)查詢，如果轉(zhuǎn)換次數(shù)等于子數(shù)組的長(zhǎng)度減 1，則該子數(shù)組是特殊的，我們返回 true。否則，我們返回 false。

時(shí)間復(fù)雜度：

• 預(yù)處理奇偶校驗(yàn)轉(zhuǎn)換需要 O(n)。
• 構(gòu)造前綴和數(shù)組需要 O(n)。
• 使用前綴和數(shù)組可以在 O(1) 內(nèi)回答每個(gè)查詢。
• 因此，總時(shí)間復(fù)雜度為 O(n q)，其中 n 是數(shù)組長(zhǎng)度，q 是查詢次數(shù)。

該解決方案通過(guò)優(yōu)化的方法有效地處理了問(wèn)題約束。

聯(lián)系鏈接

如果您發(fā)現(xiàn)本系列有幫助，請(qǐng)考慮在 GitHub 上給 存儲(chǔ)庫(kù) 一個(gè)星號(hào)或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？。您的支持對(duì)我來(lái)說(shuō)意義重大！

如果您想要更多類似的有用內(nèi)容，請(qǐng)隨時(shí)關(guān)注我：

• 領(lǐng)英
• GitHub

---

1. 子數(shù)組 子數(shù)組 是數(shù)組中連續(xù)的元素序列。??

以上是特殊陣列II的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！