文章目录
前言
解题思路
代码
前言
你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
有序表
非常方便的查到所有数字最小值，也可以非常方便的查到所有数字的最大直
每个数组中的第一个数加入有序表, 取出最大值跟最小值,可以找到一个区间
这个区间一定每个数组都有一个数落在这个区间上
然后删除最小值,把这个最小值来自数组的下一个值加入有序表,排序后重新取出最小值跟最大值
构成一个新的区间,跟之前的区间比较是否更优
当你有一个数组耗尽了,不用再继续了，你找到的最窄区间出来了
每个数组的第一个数进入有序表
7进入有序表,把1淘汰,最小区间更新
最后把所有数字都遍历一遍,得到最小的区间
代码
class Solution {
public class Node{
public int value;
public int arrid;
public int index;
public Node(int v,int ai,int i){
value=v;
arrid=ai;
index=i;
}
}
public class NodeComparator implements Comparator<Node>{
public int compare(Node o1,Node o2){
return o1.value!=o2.value?o1.value-o2.value:o1.arrid-o2.arrid;
}
}
public int[] smallestRange(List<List<Integer>> nums) {
int N=nums.size();
TreeSet<Node> orderSet=new TreeSet<>(new NodeComparator());
for(int i=0;i<N;i++){
orderSet.add(new Node(nums.get(i).get(0),i,0));
}
boolean set=false;
int a=0;
int b=0;
while(orderSet.size()==N){
Node min=orderSet.first();
Node max=orderSet.last();
if(!set||(max.value-min.value<b-a)){
set=true;
a=min.value;
b=max.value;
}
min=orderSet.pollFirst();
int arrid=min.arrid;
int index=min.index+1;
if(index!=nums.get(arrid).size()){
orderSet.add(new Node(nums.get(arrid).get(index),arrid,index));
}
}
return new int[]{a,b};
}
}
