小旭讲解 LeetCode 632. 最小区间
文章目录

  • 原题
  • 思路
  • 参考

B站

原题

你有 k 个升序排列的整数数组。找到一个最小区间,使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c,则区间 [a,b] 比 [c,d] 小。

示例 1:

输入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]] 输出: [20,24] 解释:  列表 1:[4, 10, 15, 24, 26],24 在区间 [20,24] 中。 列表 2:[0, 9, 12, 20],20 在区间 [20,24] 中。 列表 3:[5, 18, 22, 30],22 在区间 [20,24] 中。

注意:

  • 给定的列表可能包含重复元素,所以在这里升序表示 >= 。
  • 1 <= k <= 3500
  • 10^{-5} <= 元素的值 <= 10^5

思路

重要的是,正如视频中提到的,该如何想到使用多指针的方式来解决这个题目。

将原问题转变成在 k 个列表中定位一个值,并组成集合 S。此时,自然集合中的元素是由 k 个列表中的值组成。那么当前集合 S 中的最大值与最小值的差值即为求解区间的大小。那么,当 S 中的差值最小时的长度,即为问题求解的最小区间的答案。

维护 k 个指针,指向每一个列表中第一个元素的位置。因为数组具有单调性,我们可以按照如下方式进行迭代,进而找到最小区间:

  • 维护最小区间:k 个指针指向的元素中的最小值与最大值之差
  • 将最小值所在的位置向右移动
  • 当某一个指针超出所在列表长度时,跳出循环

代码

vector<vector<int>> _nums; struct cmp{     bool operator() (const pair<int, int>& a, const pair<int, int>& b) {         return _nums[a.first][a.second] > _nums[b.first][b.second];     } }; class Solution { public:     vector<int> smallestRange(vector<vector<int>>& nums) {         // 4 10 15         // 0 9 12         // 5 18 22         // 最小堆 {4, 0, 5} -> {4, 9, 5}         //                 -> {10, 0, 5}         _nums = nums;         priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;         int ma = -1e5, l = -1e5, r = 1e5;         for (int i = 0; i < nums.size(); ++i) {             pq.push({i, 0});             ma = max(ma, nums[i][0]);         }         while (true) {             auto pa = pq.top();             pq.pop();             if (ma - nums[pa.first][pa.second] < r - l) {                 l = nums[pa.first][pa.second], r = ma;             }             if (++pa.second >= nums[pa.first].size()) break;             pq.push(pa);             ma = max(ma, nums[pa.first][pa.second]);         }         return {l, r};     } };

复杂度分析

时间复杂度:O(k * n * logk) n 为列表平均长度,k 为列表个数
空间复杂度:O(k)

参考

[1]. LeetCode 原题. https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists/

小旭讲解 LeetCode 632. 最小区间leetcode刷题题解部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 小旭讲解 LeetCode 632. 最小区间leetcode刷题题解