题目描述：

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. -10⁵ <= value of elements <= 10⁵.
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.

题目大意：

给定k组递增排列的整数。求最小范围，使得每组数中至少有一个包含在其中。

解题思路：

解法I 滑动窗口（Sliding Window）

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

字典cover维护映射idx -> set(num)，记录当前窗口覆盖了哪些列表，以及这些列表中包含的数字

snum为nums去重和排序的结果

初始令窗口范围start = end = 0

重复以下过程，直到start == len(snum) 或者end == len(snum)为止

  令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:
                dmap[num].add(idx)
        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]]:
                    cover[idx].add(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

解法II 优先队列（Priority Queue）

思路类似于Merge k Sorted Lists

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

将Point(nums[i][0], i)依次加入优先队列pq（小顶堆，key为Point.x）

变量max记录当前队列中出现过的最大值

循环直到pq的size < nums.size()

  弹出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);
            pq.add(new Point(num, i));
            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]);
                pq.add(first);
                max = Math.max(max, first.x);
            }
        }
        return new int[]{start, end};
    }

}

 

本文链接：http://bookshadow.com/weblog/2017/07/02/leetcode-smallest-range/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码