leetcode-632. 最小区间

2023-12-30 17:08

文章标签 leetcode 最小区间 632

本文主要是介绍leetcode-632. 最小区间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

你有 k 个升序排列的整数列表。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例：

输入：[[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] 中。

提示：

给定的列表可能包含重复元素，所以在这里升序表示 >= 。
1 <= k <= 3500
-10^5 <= 元素的值 <= 10^5
对于使用Java的用户，请注意传入类型已修改为List<List<Integer>>。重置代码模板后可以看到这项改动。

解题思路

暴力版：
每次的区间，覆盖所有整数列表指向当前位置的值，然后每次将最小的那个位置向前移动。

拿用例来说：
第一次是[4, 0, 5]，则区间为[0, 4]，将最小的0对应的位置向后走，
第二次是[4, 9, 5]，则区间为[4, 9]，将最小的4对应的位置向后走，
第三次是[10, 9, 5]，则区间为[5, 10]，将最小的5对应的位置向后走……
以此类推，直到某个列表走到头为止

设整数列表中，最短的列表长度为l，则时间复杂度是l * k

这种方法超时了

超时的原因有2个，1个是while循环里用的all，每次循环都会对k个列表进行判断，另外1个是求区间左边界和右边界的时候需要用max, min，时间复杂度也比较高

改进：

针对while循环中的all：本意是用来检查列表是否走到头，所以可以考虑将每个列表的下标放在数据结构里，在循环内部判断是否到达该列表的最后一个值，while循环改用while True
求最小值时，需要每次从一堆数中求出最小值，然后把最小值扔掉，再放新的数，再求最小值。这个可以用堆来解决。
求最大值时，实际上只需要保存当前的最大值，并且当新加入的数比当前的最大值大时，更新最大值即可，不需要对所有数反复求最大值

Sliding window

Use the index to mark all the numbers, and sort all the numbers. Use a sliding window to go through all of them, if the current window has covered all the indexes, that means we have a answer candidate, shrink the window. Otherwise, expand the window.

Time complexity: $o(n\log n)$ for sorting.
Time complexity: $o (n)$

代码

超时普通版：

class Solution:def smallestRange(self, nums: List[List[int]]) -> List[int]:n = len(nums)index_list = [0] * nans = [-10 ** 5, 10 ** 5]while all(index_list[i] < len(nums[i]) for i in range(n)):interval_left, min_index = min((nums[i][index_list[i]], i) for i in range(n))interval_right = max(nums[i][index_list[i]] for i in range(n))ans = min(ans, [interval_left, interval_right], key = lambda x: x[1] - x[0])index_list[min_index] += 1return ans

改进版：

class Solution:def smallestRange(self, nums: List[List[int]]) -> List[int]:n = len(nums)ans = [-10 ** 5, 10 ** 5]min_heap = []interval_right = 0for i in range(n):heapq.heappush(min_heap, (nums[i][0], i, 0))interval_right = max(interval_right, nums[i][0])while True:interval_left, num_index, index = heapq.heappop(min_heap)ans = min(ans, [interval_left, interval_right], key = lambda x: x[1] - x[0])if index == len(nums[num_index]) - 1:breakinterval_right = max(interval_right, nums[num_index][index + 1])heapq.heappush(min_heap, (nums[num_index][index + 1], num_index, index + 1))return ans

Sliding Window

class Solution:def smallestRange(self, nums: List[List[int]]) -> List[int]:num_index = []for i, sublist in enumerate(nums):for each_num in sublist:num_index.append((each_num, i))num_index.sort(key=lambda x: x[0])res = []left = 0cover_index = {}for right in range(len(num_index)):add_item = num_index[right]cover_index[add_item[1]] = cover_index.get(add_item[1], 0) + 1while len(cover_index) == len(nums):interval = [num_index[left][0], num_index[right][0]]if not res or interval[1] - interval[0] < res[1] - res[0]:res = intervalpop_item = num_index[left]cover_index[pop_item[1]] -= 1if cover_index[pop_item[1]] == 0:cover_index.pop(pop_item[1])left += 1return res