[LeetCode] 632. Smallest Range Covering Elements from K Lists

[grandyang]

 

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<List>. And after you reset the code template, you'll see this point.

 

这道题给了我们一些数组，都是排好序的，让求一个最小的范围，使得这个范围内至少会包括每个数组中的一个数字。虽然每个数组都是有序的，但是考虑到他们之间的数字差距可能很大，所以最好还是合并成一个数组统一处理比较好，但是合并成一个大数组还需要保留其原属数组的序号，所以大数组中存pair对，同时保存数字和原数组的序号。然后重新按照数字大小进行排序，这样问题实际上就转换成了求一个最小窗口，使其能够同时包括所有数组中的至少一个数字。这不就变成了那道 Minimum Window Substring。所以说啊，这些题目都是换汤不换药的，总能变成我们见过的类型。这里用两个指针 left 和 right 来确定滑动窗口的范围，还要用一个 HashMap 来建立每个数组与其数组中数字出现的个数之间的映射，变量 cnt 表示当前窗口中的数字覆盖了几个数组，diff 为窗口的大小，让 right 向右滑动，然后判断如果 right 指向的数字所在数组没有被覆盖到，cnt 自增1，然后 HashMap 中对应的数组出现次数自增1，然后循环判断如果 cnt 此时为k(数组的个数)且 left 不大于 right，那么用当前窗口的范围来更新结果，然后此时想缩小窗口，通过将 left 向右移，移动之前需要减小 HashMap 中的映射值，因为去除了数字，如果此时映射值为0了，说明有个数组无法覆盖到了，cnt 就要自减1。这样遍历后就能得到最小的范围了，参见代码如下：

 

解法一：

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        vector<int> res;
        vector<pair<int, int>> v;
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); ++i) {
            for (int num : nums[i]) {
                v.push_back({num, i});
            }
        }
        sort(v.begin(), v.end());
        int left = 0, n = v.size(), k = nums.size(), cnt = 0, diff = INT_MAX;
        for (int right = 0; right < n; ++right) {
            if (m[v[right].second] == 0) ++cnt;
            ++m[v[right].second];
            while (cnt == k && left <= right) {
                if (diff > v[right].first - v[left].first) {
                    diff = v[right].first - v[left].first;
                    res = {v[left].first, v[right].first};
                } 
                if (--m[v[left].second] == 0) --cnt;
                ++left;
            }
        }
        return res;
    }
};

 

这道题还有一种使用 priority_queue 来做的，优先队列默认情况是最大堆，但是这道题我们需要使用最小堆，重新写一下 comparator 就行了。解题的主要思路很上面的解法很相似，只是具体的数据结构的使用上略有不同，这 curMax 表示当前遇到的最大数字，用一个 idx 数组表示每个 list 中遍历到的位置，然后优先队列里面放一个pair，是数字和其所属list组成的对儿。遍历所有的list，将每个 list 的首元素和该 list 序号组成 pair 放入队列中，然后 idx 数组中每个位置都赋值为1，因为0的位置已经放入队列了，所以指针向后移一个位置，还要更新当前最大值 curMax。此时 queue 中是每个 list 各有一个数字，由于是最小堆，所以最小的数字就在队首，再加上最大值 curMax，就可以初始化结果 res 了。然后进行循环，注意这里循环的条件不是队列不为空，而是当某个 list 的数字遍历完了就结束循环，因为范围要 cover 每个 list 至少一个数字。所以 while 循环条件即是队首数字所在的 list 的遍历位置小于该 list 的总个数，在循环中，取出队首数字所在的 list 序号t，然后将该 list 中下一个位置的数字和该 list 序号t组成 pair，加入队列中，然后用这个数字更新 curMax，同时 idx 中t对应的位置也自增1。现在来更新结果 res，如果结果 res 中两数之差大于 curMax 和队首数字之差，则更新结果 res，参见代码如下：

 

解法二：

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int curMax = INT_MIN, n = nums.size();
        vector<int> idx(n, 0);
        auto cmp = [](pair<int, int>& a, pair<int, int>& b) {return a.first > b.first;};
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp) > q(cmp);
        for (int i = 0; i < n; ++i) {
            q.push({nums[i][0], i});
            idx[i] = 1;
            curMax = max(curMax, nums[i][0]);
        }
        vector<int> res{q.top().first, curMax};
        while (idx[q.top().second] < nums[q.top().second].size()) {
            int t = q.top().second; q.pop();
            q.push({nums[t][idx[t]], t});
            curMax = max(curMax, nums[t][idx[t]]);
            ++idx[t];
            if (res[1] - res[0] > curMax - q.top().first) {
                res = {q.top().first, curMax};
            }
        }
        return res;
    }
};

 

Github 同步地址：

#632

 

类似题目：

Minimum Window Substring

 

参考资料：

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/discuss/104893/Java-Code-using-PriorityQueue.-similar-to-merge-k-array

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/discuss/104886/Clean-C%2B%2B-priority_queue-solution-using-iterators

 

LeetCode All in One 题目讲解汇总(持续更新中...)