0632._Smallest_Range.md

632. Smallest Range

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/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:
The given list may contain duplicates, so ascending order means >= here.
1 <= k <= 3500
-105 <= value of elements <= 105.
For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.

解题方案

思路 1 - 时间复杂度: O(row * col * lg(col))- 空间复杂度: O(col)******

把nums看成一个matrix

维护一个最小堆，然后把第一列的每个元素和它对应的i,j（即坐标）丢进去，然后第一列中的最大值就是我们当前 smallest range 的右边界

接下来我们慢慢pop堆，不停更新smallest range，这样就可以保证每个list中至少有一个元素在smallest range里面了

因为我们最坏情况要处理完整个matrix中的所有点，并且处理每一个点的时候都要heappop和heappush一次，时间复杂度为O(row * col * lg(col))

参考awice

beats 91.50%

class Solution:
    def smallestRange(self, nums):
        """
        :type nums: List[List[int]]
        :rtype: List[int]
        """
        heap = [(lst[0], i, 0) for i, lst in enumerate(nums)]
        heapq.heapify(heap)
        
        res = [-sys.maxsize, sys.maxsize]
        right = max(lst[0] for lst in nums)
        while heap:
            left, i, j = heapq.heappop(heap)
            if right - left < res[1] - res[0]:
                res = [left, right]
            if j == len(nums[i]) - 1:
                return res
            nxt = nums[i][j+1]
            right = max(right, nxt)
            heapq.heappush(heap, (nxt, i, j+1))