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

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

難度：難

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

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

如果 b - a 或 a

c 如果 b - a == d - c。

範例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)。

此解有效地找到包含 k 個排序清單中每個清單中至少一個數字的最小範圍。

聯絡連結

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

一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

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

• 領英
• GitHub

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