数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中 K 个列表的最小范围覆盖元素
假设我们有 k 个排序整数列表。我们需要搜索包含来自这 k 个列表中每个列表至少一个数字的最小范围。这里范围 [a,b] 小于范围 [c,d]，当 b-a < d-c 或 a < c 当 b-a == d-c 时。
因此，如果输入类似于 [[4,10,15,25,26],[0,9,14,20],[5,18,24,30]]，则输出将为 [14, 18]
为了解决这个问题，我们将遵循以下步骤 -
- minRange := inf, maxRange := -inf, rangeSize := inf, tempMinRange := inf, tempMaxRange := -inf
- n := nums 的大小
- 定义一个大小为 n 的数组 pointers
- 创建一个优先级队列 pq
- 对于初始化 i := 0，当 i < n，更新（i 增加 1），执行 -
- 将 { nums[i, 0], i } 插入 pq
- tempMaxRange := tempMaxRange 和 nums[i, 0] 的最大值
- 当 1 不为零时，执行 -
- 定义一个对 temp := pq 的顶部
- 从 pq 中删除元素
- tempMinRange := temp.first
- idx := temp 的第二个元素
- 如果 tempMaxRange - tempMinRange < rangeSize，则 -
- rangeSize := tempMaxRange - tempMinRange
- minRange := tempMinRange
- maxRange := tempMaxRange
- （pointers[idx] 增加 1）
- 如果 pointers[idx] 与 nums[idx] 的大小相同，则 -
- 退出循环
- 否则
- tempMaxRange := tempMaxRange 和 nums[idx, pointers[idx]] 的最大值
- 将 { nums[idx, pointers[idx]], idx } 插入 pq
- 定义一个大小为 2 的数组 ans
- ans[0] := minRange, ans[1] := maxRange
- 返回 ans
让我们看看以下实现以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
struct Comparator{
bool operator() (pair <int, int> a, pair <int, int> b){
return !(a.first < b.first);
}
};
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
int minRange = INT_MAX;
int maxRange = INT_MIN;
int rangeSize = INT_MAX;
int tempMinRange, tempMaxRange, tempRangeSize;
tempMinRange = INT_MAX;
tempMaxRange = INT_MIN;
int n = nums.size();
vector <int> pointers(n);
priority_queue < pair <int, int>, vector < pair <int, int> >, Comparator > pq;
for(int i = 0; i < n; i++){
pq.push({nums[i][0], i});
tempMaxRange = max(tempMaxRange, nums[i][0]);
}
while(1){
pair <int, int> temp = pq.top();
pq.pop();
tempMinRange = temp.first;
int idx = temp.second;
if(tempMaxRange - tempMinRange < rangeSize){
rangeSize = tempMaxRange - tempMinRange;
minRange = tempMinRange;
maxRange = tempMaxRange;
}
pointers[idx]++;
if(pointers[idx] == nums[idx].size())break;
else{
tempMaxRange = max(tempMaxRange, nums[idx][pointers[idx]]);
pq.push({nums[idx][pointers[idx]], idx});
}
}
vector <int> ans(2);
ans[0] = minRange;
ans[1] = maxRange;
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{4,10,15,25,26},{0,9,14,20},{5,18,24,30}};
print_vector(ob.smallestRange(v));
}输入
{{4,10,15,25,26},{0,9,14,20},{5,18,24,30}};输出
[14, 18, ]
更新于: 2020-06-01
212 次查看
广告