3152。特殊陣列II

難度：中

主題：陣列、二分查找、前綴和

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

給定一個整數(shù)數(shù)組和一個2D 整數(shù)矩陣查詢，其中對於requests[i] = [from_i, to_i]，你的任務是檢查子數(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]]
• 輸出： [假，真]
• 說明：

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

約束：

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

提示：

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

解：

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

方法：

1. 辨識奇偶校驗躍遷： 我們可以對陣列進行預處理來標記奇偶校驗發(fā)生變化的位置。例如：
   0代表偶數(shù)。
   1代表奇數(shù)。

這個想法是識別相鄰元素具有不同奇偶性的所有位置。這將幫助我們透過檢查查詢中的位置是否屬於同一「特殊」區(qū)塊來有效地確定子數(shù)組是否特殊。

1. 預處理： 建立一個二進位數(shù)組 parity_change，其中如果相鄰元素具有不同的奇偶校驗，則每個元素為 1，否則為 0。例如：
   

   • 如果 nums[i] 和 nums[i 1] 奇偶校驗不同，則設定 parity_change[i] = 1，否則為 0。

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

3. 查詢處理：
   對於每個查詢 [from, to]，檢查 [from, to-1] 範圍內(nèi)是否存在奇偶校驗不變的位置。這可以透過檢查前綴總和值的差異來完成： prefix_sum[to] - prefix_sum[from].

讓我們用 PHP 實作這個解：3152。特殊陣列II

解釋：

1. 預處理奇偶校驗轉(zhuǎn)換：
   如果元素 nums[i] 和 nums[i 1] 有不同的奇偶校驗，我們計算 parity_change[i] = 1。否則，我們將其設為 0。

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

1. 查詢評估： 對於每個查詢，如果轉(zhuǎn)換次數(shù)等於子數(shù)組的長度減 1，則該子數(shù)組是特殊的，我們傳回 true。否則，我們回傳 false。

時間複雜度：

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

此解決方案透過最佳化的方法有效地處理了問題約束。

聯(lián)絡連結(jié)

如果您發(fā)現(xiàn)本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網(wǎng)絡上分享該帖子？ 。您的支持對我來說意義重大！

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

• 領(lǐng)英
• GitHub

---

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

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