你有 k 個升序排列的整數(shù)數(shù)組。找到一個最小區(qū)間，使得 k 個列表中的每個列表至少有一個數(shù)包含在其中。

我們定義如果 b-a < d-c 或者在 b-a == d-c 時 a < c，則區(qū)間 [a,b] 比 [c,d] 小。

示例 1:

輸入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
輸出: [20,24]

**解釋: **

列表 1：[4, 10, 15, 24, 26]，24 在區(qū)間 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在區(qū)間 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在區(qū)間 [20,24] 中。

注意:

給定的列表可能包含重復元素，所以在這里升序表示 >= 。

1 <= k <= 3500

-105 <= 元素的值 <= 105

堆

給定 k 個列表，需要找到最小區(qū)間，使得每個列表都至少有一個數(shù)在該區(qū)間中。該問題可以轉(zhuǎn)化為，從 k 個列表中各取一個數(shù)，使得這 k 個數(shù)中的最大值與最小值的差最小。

假設這 k 個數(shù)中的最小值是第 i 個列表中的 x，對于任意 j != i，設第 j 個列表中被選為 k 個數(shù)之一的數(shù)是 y，則為了找到最小區(qū)間，y 應該取第 j 個列表中大于等于 x 的最小的數(shù)。

簡單證明如下：假設 z 也是第 j 個列表中的數(shù)，且 z>y，則有 z-x>y-x，同時包含 x 和 z 的區(qū)間一定不會小于同時包含 x 和 y 的區(qū)間。因此，其余 k?1 個列表中應該取大于等于 x 的最小的數(shù)。

由于 k 個列表都是升序排列的，因此對每個列表維護一個指針，通過指針得到列表中的元素，指針右移之后指向的元素一定大于或等于之前的元素。

使用最小堆維護 k 個指針指向的元素中的最小值，同時維護堆中元素的最大值。初始時，k 個指針都指向下標 0，最大元素即為所有列表的下標 0 位置的元素中的最大值。

每次從堆中取出最小值，根據(jù)最大值和最小值計算當前區(qū)間，如果當前區(qū)間小于最小區(qū)間則用當前區(qū)間更新最小區(qū)間，然后將對應列表的指針右移，將新元素加入堆中，并更新堆中元素的最大值。

如果一個列表的指針超出該列表的下標范圍，則說明該列表中的所有元素都被遍歷過，堆中不會再有該列表中的元素，因此退出循環(huán)。

Code

def smallestRange(self, nums: List[List[int]]) -> List[int]:rangeLeft, rangeRight = -10 ** 9, 10 ** 9# 初始時，k 個指針都指向下標 0，最大元素即為所有列表的下標 0 位置的元素中的最大值maxValue = max(vec[0] for vec in nums)priorityQueue = [(vec[0], i, 0) for i, vec in enumerate(nums)]heapq.heapify(priorityQueue)while True:minValue, row, idx = heapq.heappop(priorityQueue)if maxValue - minValue < rangeRight - rangeLeft:rangeLeft, rangeRight = minValue, maxValueif idx == len(nums[row]) - 1:breakmaxValue = max(maxValue, nums[row][idx + 1])heapq.heappush(priorityQueue, (nums[row][idx + 1], row, idx + 1))return [rangeLeft, rangeRight]

復雜度分析

時間復雜度：O(nklogk)，其中 n 是所有列表的平均長度，k 是列表數(shù)量。所有的指針移動的總次數(shù)最多是 nk 次，每次從堆中取出元素和添加元素都需要更新堆，時間復雜度是 O(logk)，因此總時間復雜度是 O(nklogk)。

空間復雜度：O(k)，其中 k 是列表數(shù)量。空間復雜度取決于堆的大小，堆中維護 k 個元素。

總結(jié)

以上是生活随笔為你收集整理的632. Smallest Range Covering Elements from K Lists 最小区间的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。