。 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中文网其他相关文章！