632.Smallest Range Covering Elements from K Lists

Tags: Hard Hash Table Two Pointers String

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

---

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.

---

这道题其实可以转化成从k个列表里面，每个列表里选一个数，让这k个数的最大值和最小只差最小。联想到合并k个有序链表，则可能使用优先级队列来进行优化。用一个小根堆来维护最小值，用next数组来维护探测到某个列表的具体位置，小根堆需要我们自己去定义优先级规则。时间复杂度$O(n \log{k})$。

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        int resLeft = 0, resRight = INT_MAX;
        vector<int> next(n, 0);

        auto cmp = [&] (const int & a, const int & b) {
            return nums[a][next[a]] > nums[b][next[b]];
        };

        int minValue = INT_MAX, maxValue = INT_MIN;
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
        for (int i = 0; i < n; ++i) {
            pq.push(i);
            maxValue = max(maxValue, nums[i][0]);
        }

        while (true) {
            int tmp = pq.top(); pq.pop();
            minValue = nums[tmp][next[tmp]];

            int gap1 = maxValue - minValue, gap2 = resRight - resLeft;
            if (gap1 < gap2 || (gap1 == gap2 && minValue < resLeft)) {
                resLeft = minValue, resRight = maxValue;
            }

            if (next[tmp] == (int)nums[tmp].size() - 1) break;

            ++next[tmp];
            maxValue = max(maxValue, nums[tmp][next[tmp]]);
            pq.push(tmp);
        }

        return vector<int>{resLeft, resRight};
    }
};

第二种解法就是可以先将这k个列表合并成一个列表，然后寻找一个长度最短的子数组，这个子数组至少包含每个列表中的一个元素，完全就可以用哈希表来做，这样时间复杂度就是$O(nk)$。这也就解释了为什么标签里还有Hash Table和Two Pointers的标签。

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;
    }
};