特殊陣列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

解釋：

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

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

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

時間複雜度：

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

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

聯絡連結

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

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

---

1. 子數組 子數組 是數組中連續的元素序列。 ↩

以上是特殊陣列II的詳細內容。更多資訊請關注PHP中文網其他相關文章！