標記所有元素後查找數組的分數

2593。標記所有元素後找出數組的分數

難度：中

主題：堆疊（優先權佇列）、排序、陣列、模擬、雜湊表、有序集、有序映射、貪心、單調堆疊、滑動視窗、兩個指標、堆疊、佇列、位元操作、分而治之，動態規劃，雙向鍊錶，資料流，基數排序，回溯，位元掩碼，樹，設計，雜湊函數、字串、迭代器、計數排序、鍊錶

給你一個由正整數組成的陣列 nums。

從分數 = 0 開始，應用以下演算法：

• 選擇數組中未標記的最小整數。如果有平局，則選擇索引最小的一個。
• 將所選整數的值加到分數中。
• 標記所選元素及其兩個相鄰元素（如果存在）。
• 重複，直到所有陣列元素都被標記。

回傳應用上述演算法後得到的分數。

範例1：

• 輸入： nums = [2,1,3,4,5,2]
• 輸出： 7
• 說明：我們將元素進行如下標記：
  • 1 是最小的未標記元素，因此我們標記它及其兩個相鄰元素：[2,1,3,4,5,2].
  • 2 是最小的未標記元素，因此我們標記它及其左相鄰元素：[2,1,3,4,5,2].
  • 4 是唯一剩餘的未標記元素，因此我們將其標記為：[2,1,3,4,5,2].
  • 我們的分數是 1 2 4 = 7。

範例2：

• 輸入： nums = [2,3,5,1,3,2]
• 輸出： 5
• 說明：我們將元素進行如下標記：
  • 1 是最小的未標記元素，因此我們標記它及其兩個相鄰元素：[2,3,5,1,3,2].
  • 2是最小的未標記元素，因為有兩個，所以我們選擇最左邊的一個，所以我們標記索引為0的那個及其右鄰元素：[2,3,5,1,3, 2 ].
  • 2 是唯一剩餘的未標記元素，因此我們將其標記為：[2,3,5,1,3,2].
  • 我們的分數是 1 2 2 = 5。

約束：

• 1 5
• 1 6

提示：

1. 嘗試模擬標記元素及其相鄰元素的過程。
2. 如果有一個元素已經被標記，那麼你就跳過它。

解：

我們可以透過使用排序數組或優先權佇列來追蹤最小的未標記元素來有效地模擬標記過程。所以我們可以用以下方法：

計劃：

1. 輸入解析：讀取陣列nums並初始化分數和標記狀態變數。
2. 堆（優先權隊列）：
   • 使用最小堆高效提取每一步中最小的未標記元素。
   • 將每個元素及其索引（值、索引）插入堆中，以根據最小索引管理關係。
3. 標記元素：
   • 維護一個標記數組來追蹤某個元素及其相鄰元素是否被標記。
   • 處理堆中的元素時，如果已標記則跳過它。
   • 標記目前元素及其兩個相鄰元素（如果存在）。
   • 將目前元素的值加到分數中。
4. 重複：繼續，直到所有元素都被標記。
5. 輸出：傳回累計分數。

讓我們用 PHP 實作這個解：2593。標記所有元素後找出數組的分數

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

// Example usage:
$nums1 = [2, 1, 3, 4, 5, 2];
$nums2 = [2, 3, 5, 1, 3, 2];

echo findScore($nums1) . "\n"; // Output: 7
echo findScore($nums2) . "\n"; // Output: 5
?>

解釋：

1. 堆建:

   • usort 函數會根據值對陣列進行排序，並在值綁定時按索引對陣列進行排序。
   • 這確保我們始終處理具有最小索引的最小未標記元素。

2. 標記邏輯:

   • 對於每個未標記的元素，我們使用標記的陣列來標記它及其相鄰元素。
   • 這確保我們有效地跳過先前標記的元素。

3. 時間複雜度:

   • 將堆排序：O(n log n)
   • 處理堆：O(n)
   • 整體而言：O(n log n)，這對於給定的限制是有效的。

4. 空間複雜度:

   • 標記數組：O(n)
   • 堆：O(n)
   • 總計：O(n)

此解決方案滿足約束條件，並且對於大輸入有效地工作。

聯絡連結

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

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

• 領英
• GitHub

以上是標記所有元素後查找數組的分數的詳細內容。更多資訊請關注PHP中文網其他相關文章！