。 K 清單中的最小範圍覆蓋元素

632。 K 個清單中的最小範圍覆蓋元素

難度：難

主題：陣列、雜湊表、貪婪、滑動視窗、排序、堆疊（優先權佇列）

你有 k 個按 非遞減順序排序的整數列表。找出 最小 範圍，其中至少包含 k 個清單中每個清單中的一個數字。

如果 b - a 或 a

範例1：

• 輸入：
nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
• 輸出：
[20,24]
• 說明：
  列表 1：[4, 10, 15, 24,26]，24 在範圍 [20,24] 內。
  列表 2：[0, 9, 12, 20]，20 在範圍 [20,24] 內。
  列表 3：[5, 18, 22, 30]，22 在範圍 [20,24] 內。

範例2：

• 輸入：
nums = [[1,2,3],[1,2,3],[1,2,3]]
• 輸出：
[1,1]

約束：

nums.length == k
1 1 ^-105 5
• nums[i] 依非遞減
順序排序。

解：

我們可以使用 min-heap

1. 最小堆初始化
：使用最小堆來儲存 k 個列表中每個列表中的目前元素。每個堆條目都是一個元組，其中包含值、它來自的列表的索引以及該列表中元素的索引。
2. 最大值追蹤
：追蹤目前視窗中的最大值。這很重要，因為範圍是由最小元素（來自堆）和當前最大值之間的差異決定的。
3. 迭代直到列表末尾
   ：對於每次迭代：
   從堆中提取最小元素。
   如果目前範圍[min_value, max_value]小於先前記錄的最小範圍，則更新範圍。
   移至清單中從中取得最小元素的下一個元素。更新最大值並將新元素加入到堆中。
4. 終止
：當任何清單耗盡時，進程結束。

讓我們用 PHP 實作這個解：632。 K 列表中的最小範圍覆蓋元素

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

// Example usage:
$nums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]];
$result = smallestRange($nums);
print_r($result); // Output: [20, 24]
?>

1. 堆初始化
   ：
   初始堆包含每個清單中的第一個元素。我們也追蹤第一個元素中的最大元素。
2. 處理堆
   ：
   從堆中提取最小元素，然後嘗試透過新增相同清單中的下一個元素（如果可用）來擴展範圍。
   在堆中加入新元素後，如果新元素更大，則更新 maxValue。
   每當 maxValue 和 minValue 之間的差值小於先前記錄的範圍時，更新最小範圍。
3. 終止
   ：
   當任何清單用完元素時循環就會停止，因為我們不能再包含該範圍內的所有清單。

• 時間複雜度
：O(n * log k)，其中n是所有清單中的元素總數，k是列表的數量。複雜性來自於在堆中插入和刪除元素。
• 空間複雜度
：在堆中儲存元素的O(k)。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫

• 領英
• GitHub

以上是。 K 清單中的最小範圍覆蓋元素的詳細內容。更多資訊請關注PHP中文網其他相關文章！