Leetcode 632：Smallest Range Covering Elements from K Lists（最小区间）**
地址 题目的👍数：1178
题目的👎数：25
1. 问题描述：
你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
输入：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、方法：滑动窗口法
将K个整数列表的信息保留在一个list集合中，我们可以创建一个新的数据结构 Pair(int num,int index)来记录这些信息，其中num代表的是保存的整数，index代表的是列表的序号给这个list排序，根据的是num的大小双指针遍历list（滑动窗口）： 1）我们需要找到一个包含了所有的列表窗口，这一步通过end指针后移实现，并且用一个计数器记录访问到的列表数目，当计数器达到n个时，说明找到了符合条件的窗口。 2）找到窗口之后，start后移，直到计数器小于n时，说明此时的窗口已经不符合要求了，跳转到 1），在这之前，窗口一直是满足条件的，通过比较来更新结果
3、代码
class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
//滑动窗口问题
//使用1个list记录所有的数字和index
List<Pair> all = new ArrayList<>();
for(int i = 0;i<nums.size();++i) {
for(int j = 0;j<nums.get(i).size();++j) {
all.add(new Pair(nums.get(i).get(j),i));
}
}
//排序
Collections.sort(all,new Comparator<>() {
@Override
public int compare(Pair p1,Pair p2) {
if(p1.num < p2.num) return -1;
if(p1.num > p2.num) return 1;
return 0;
}
});
int[] rec = new int[nums.size()];//记录此区间访问到哪些列表
int minLength = Integer.MAX_VALUE;//最短区间长度
int[] res = new int[]{0,0};//结果
int start = 0;//双指针
int end = 0;
int count = 0;//记录访问到了多少个列表，访问到n个说明全部包括了
//双指针遍历
while(start < all.size() && end < all.size()) {
//找到包含所有列表的区间
while(count < nums.size() && end < all.size()) {
int index = all.get(end).index;
if(rec[index] == 0) ++count;
++rec[index];
++end;
}
//不断缩短区间，直至不再包含所有列表，进入下一轮迭代
while(count == nums.size()) {
int left = all.get(start).num;
int right = all.get(end-1).num;
if(right - left < minLength) { //总是记录着最小的长度
minLength = right-left;
res[0] = left;
res[1] = right;
}
int index = all.get(start).index;
--rec[index];
if(rec[index] == 0) --count;
++start;
}
}
return res;
}
class Pair {
int num;
int index;
public Pair(int num,int index) {
this.num = num;
this.index = index;
}
@Override
public String toString() {
return "[ " + Integer.toString(num) + " " + Integer.toString(index) + " ]";
}
}
}
4、复杂度
时间复杂度 ：排序的复杂度时O(nlogn)，遍历的复杂度为O(n)空间复杂度：使用了一个List，一个array，复杂度都为O(n)
