深圳制作网站怎么样,东莞有哪些好的网站建设公司,试用虚拟主机不能创建网站,网络营销案例分析及答案文章目录1. 题目2. 解题1. 题目
你有 k 个升序排列的整数数组。 找到一个最小区间#xff0c;使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a d-c 或者在 b-a d-c 时 a c#xff0c;则区间 [a,b] 比 [c,d] 小。
示例 1:
输入:[[4,10,15,…
文章目录1. 题目2. 解题1. 题目
你有 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
把数字和其区间的编号存入vector并排序滑动窗口方法保证窗口内有 k 个区间的数记录最小差的左右端点值
class Solution {
public:vectorint smallestRange(vectorvectorint nums) {vectorvectorint v;int k nums.size();for(int i 0; i nums.size(); i){for(int n : nums[i])v.push_back({n,i});//num 区间编号}sort(v.begin(), v.end());unordered_mapint,int m;//区间编号该区间有多少个数在窗口内int i 0, j 0, n v.size();int l -1e7, r 1e7;while(j n){if(m.size() k)m[v[j][1]];while(m.size() k){if(v[j][0]-v[i][0] r-l){l v[i][0];r v[j][0];}if(--m[v[i][1]] 0)m.erase(v[i][1]);i;}j;}return {l, r};}
};496 ms 24.5 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
