题意
你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
Solution
直接对所有的数排序，然后优先队列维护一个k个数组都有值存在且对当前来说长度最小的滑动窗口，同时维护答案即可。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| class Solution {
class Node {
public Node(int val, int id) {
this.val = val;
this.id = id;
}
int val, id;
}
public int[] smallestRange(List<List<Integer>> nums) {
int n = nums.size();
PriorityQueue<Node> q = new PriorityQueue<>(new Comparator<Node>(){
@Override
public int compare(Node a, Node b) {
return a.val - b.val;
}
});
PriorityQueue<Node> q1 = new PriorityQueue<>(new Comparator<Node>(){
@Override
public int compare(Node a, Node b) {
return a.val - b.val;
}
});
for (int i = 0; i < n; i++) {
List<Integer> num = nums.get(i);
for (int j = 0; j < num.size(); j++) {
Node node = new Node(num.get(j), i);
q.add(node);
}
}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int cnt = 0, dis = 1000000000;
int[] res = new int[2];
while (q.size() > 0) {
Node now = q.poll();
q1.add(now);
if(map.get(now.id) == null) {
cnt++;
map.put(now.id, 1);
} else {
int x = map.get(now.id);
map.remove(now.id);
map.put(now.id, x + 1);
}
while(q1.size() > 0) {
Node x = q1.peek();
if(map.get(x.id) == 1)
break;
else {
q1.poll();
int y = map.get(x.id);
map.remove(x.id);
map.put(x.id, y - 1);
}
}
if(q1.size() > 0 && cnt == n && dis > now.val - q1.peek().val) {
dis = now.val - q1.peek().val;
res[0] = q1.peek().val;
res[1] = now.val;
}
}
return res;
}
}
|