最小区间
问题描述：
你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [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 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
注意:
给定的列表可能包含重复元素，所以在这里升序表示 >= 。
1 <= k <= 3500
-105 <= 元素的值 <= 105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解决方案
由题目可知，是想找到一个包含每个列表元素的子区间，即找到k个列表中尽可能接近的数，因此可以使用k路归并排序，排序过程中存储这k个列表当前元素的最小值与最大值，直到k个列表中某个列表元素全部用完，如此最小区间一定在遍历过的最小值最大值之中。
对于k个列表当前元素的最小值与最大值，直接遍历，即O（K），若数组长度记做N时，总体时间复杂度为（N * K * K），由于对每个元素均要扫描k次。
代码如下：
class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
int left = (int)-1e5;
int right = (int)1e5;
int k = nums.size();
// 用于存储k个列表的当前位置
int[] curIndex = new int[k];
int max = 0;
int min = 0;
while(true){
for(int i = 0; i < k; i++){
List<Integer> temp = nums.get(i);
if(temp.get(curIndex[i]) > nums.get(max).get(curIndex[max])){
max = i;
}
if(temp.get(curIndex[i]) < nums.get(min).get(curIndex[min])){
min = i;
}
}
if(nums.get(max).get(curIndex[max]) - nums.get(min).get(curIndex[min]) < right - left){
right = nums.get(max).get(curIndex[max]);
left = nums.get(min).get(curIndex[min]);
}
if(++curIndex[min] == nums.get(min).size()){
break;
}
}
return new int[] {left, right};
}
}直接TLE了，用堆优化喽。
对于k个列表的最小值，借助一大小为K的最小堆，每次从中弹出一最小值即为所求，弹出后再将其所在列表的下一个值加入堆中（由于弹出后需要知道该值属于哪个列表，因此不能直接在堆中存值，应存其所在的列表id）。对于最大值，由于是进行排序的因此使用一变量max保存当前堆中的最大值（入堆前判断即可）。由于借助了堆每次查找时间复杂度和插入时间复杂度均为O（log(K)），因此总体时间复杂度为O（N * K * log（K））.
代码如下：
class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
int left = (int)-1e5;
int right = (int)1e5;
int k = nums.size();
int[] curIndex = new int[k];
int max = (int)-1e5;
Queue<Integer> minHeap = new PriorityQueue(new Comparator<Integer>(){
public int compare(Integer o1, Integer o2){
return nums.get(o1).get(curIndex[o1]) - nums.get(o2).get(curIndex[o2]);
}
});
for(int i = 0; i < k; i++){
minHeap.add(i);
max = Math.max(max, nums.get(i).get(0));
}
while(true){
int cur = minHeap.remove();
if(max - nums.get(cur).get(curIndex[cur]) < right - left){
right = max;
left = nums.get(cur).get(curIndex[cur]);
}
if(++curIndex[cur] == nums.get(cur).size()){
break;
}
max = Math.max(max, nums.get(cur).get(curIndex[cur]));
minHeap.add(cur);
}
return new int[] {left, right};
}
}最后想谈一点的是，通过该问题还学习到了如此巧妙的内部类的用法。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-08-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录