## 题目描述：

LeetCode 632. Smallest Range

You have `k` lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the `k` lists.

We define the range [a,b] is smaller than range [c,d] if `b-a < d-c` or `a < c` if `b-a == d-c`.

Example 1:

```Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].
```

Note:

1. The given list may contain duplicates, so ascending order means >= here.
2. 1 <= `k` <= 3500
3. -105 <= `value of elements` <= 105.
4. For Java users, please note that the input type has been changed to List>. And after you reset the code template, you'll see this point.

## 解题思路：

```字典dmap维护映射num -> set(idx)，记录num在哪些列表（编号0~len(nums)）中出现过

snum为nums去重和排序的结果

令end向右滑动，直到cover中包含所有列表为止

令start向右滑动，直到cover中不再包含所有列表为止，并更新最小间隔和答案```

## Python代码：

``````class Solution(object):
def smallestRange(self, nums):
"""
:type nums: List[List[int]]
:rtype: List[int]
"""
dmap = collections.defaultdict(set)
cover = collections.defaultdict(set)
nsize = len(nums)

for idx, nlist in enumerate(nums):
for num in nlist:
snum = sorted(set(n for nlist in nums for n in nlist))
ssize = len(snum)

start = end = 0
ans = [snum[0], snum[-1]]
gap = 0x7FFFFFFF
while start < ssize and end < ssize:
while end < ssize and len(cover) < nsize:
for idx in dmap[snum[end]]:
end += 1
while start < ssize and len(cover) == nsize:
if len(cover) == nsize and snum[end - 1] - snum[start] < gap:
gap = snum[end - 1] - snum[start]
ans = [snum[start], snum[end - 1]]
for idx in dmap[snum[start]]:
cover[idx].remove(snum[start])
if not cover[idx]: del cover[idx]
start += 1
return ans
``````

```利用数组idxArr保存k个list的当前下标，初始为0

弹出pq的最小元素first（min, idx），用max - min更新答案

将idxArr[idx]++，若idxArr[idx] < nums[idx].size()，将(nums[idxArr[idx]], idx)加回pq```

## Java代码：

``````import java.awt.Point;

public class Solution {
public int[] smallestRange(List<List<Integer>> nums) {
PriorityQueue<Point> pq = new PriorityQueue<>((a, b) -> (a.x - b.x));
int size = nums.size();
int[] idxArr = new int[size];
int max = 0;
for (int i = 0; i < size; i++) {
int num = nums.get(i).get(0);
max = Math.max(max, num);
}
int start = -1, end = -1, gap = Integer.MAX_VALUE;
while (pq.size() == size) {
Point first = pq.poll();
int min = first.x, idx = first.y;
if (max - min < gap) {
gap = max - min;
start = min;
end = max;
}
if (++idxArr[idx] < nums.get(idx).size()) {
first.x = nums.get(idx).get(idxArr[idx]);
max = Math.max(max, first.x);
}
}
return new int[]{start, end};
}

}
``````

Pingbacks已关闭。