小旭讲解 LeetCode 632. 最小区间leetcode刷题题解
本文主要介绍小旭讲解 LeetCode 632. 最小区间leetcode刷题题解 解题思路方法,方便大家深入理解解决小旭讲解 LeetCode 632. 最小区间leetcode刷题题解 过程。本文也将分享小旭讲解 LeetCode 632. 最小区间leetcode刷题题解 所遇到的问题和应对策略,怎么解决怎么做的问题。
通过深入本文可以理解代码原理,进行代码文档的下载,也可以查看相应 Demo 动图演示。
提供Java,go,c++,python,js等在内的题解,欢迎收藏我们题解网
全网精选,每天更新,一起变大神!

文章目录
- 原题
- 思路
- 参考
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刷题题解
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 小旭讲解 LeetCode 632. 最小区间leetcode刷题题解