您的位置:首页 > 娱乐 > 明星 > 网页美工设计招聘网_日本室内设计官网_江西百度推广开户多少钱_2021年经典营销案例

网页美工设计招聘网_日本室内设计官网_江西百度推广开户多少钱_2021年经典营销案例

2025/7/14 23:04:05 来源:https://blog.csdn.net/tus00000/article/details/148749515  浏览:    关键词:网页美工设计招聘网_日本室内设计官网_江西百度推广开户多少钱_2021年经典营销案例
网页美工设计招聘网_日本室内设计官网_江西百度推广开户多少钱_2021年经典营销案例

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

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

示例 1:

输入:nums = [[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] 中。
示例 2:

输入:nums = [[1,2,3],[1,2,3],[1,2,3]]
输出:[1,1]

提示:

nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-10 5 ^5 5 <= nums[i][j] <= 10 5 ^5 5
nums[i] 按非递减顺序排列

滑动窗口,滑窗区间是所有输入数列中的最小值到最大值,窗口内包含来自所有数列的值时即找到了一个符合题意的区间,维护最小区间即可:

class Solution {
public:vector<int> smallestRange(vector<vector<int>>& nums) {unordered_map<int, unordered_set<int>> numPos;int minNum = numeric_limits<int>::max();int maxNum = 0;for (int i = 0; i < nums.size(); ++i) {minNum = min(minNum, nums[i][0]);maxNum = max(maxNum, nums[i][nums[i].size() - 1]);for (int j = 0; j < nums[i].size(); ++j) {numPos[nums[i][j]].insert(i);}}unordered_map<int, int> freq;int validListNum = 0;int left = minNum;int ansBegin = 0;int ansLen = numeric_limits<int>::max();for (int i = minNum; i <= maxNum; ++i) {for (int pos : numPos[i]) {if (++freq[pos] == 1) {++validListNum;}}while (validListNum == nums.size()) {if (i - left + 1 < ansLen) {ansBegin = left;ansLen = i - left + 1;}for (int pos : numPos[left]) {if (--freq[pos] == 0) {--validListNum;}}++left;}}vector<int> ans = {ansBegin, ansBegin + ansLen - 1};return ans;}
};

如果每个数列的平均长度为n,数列中的数字范围为m,则此算法时间复杂度为O(nk + m),空间复杂度为O(nk)。

以上代码中,从最小值一直循环到了最大值,如果范围很大,但列表中的数字数量很小,会很耗时,因此可以把每个数字及其出现位置组成一个pair,然后放到一个vector里,这样遍历vector里的数字就可以了。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com