資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在 C++ 中查詢包含來自 k 個列表的元素的最小範圍
假設我們有 k 個不同的列表。元素已排序。我們必須搜尋包含來自 k 個不同列表中至少一個數字的最小範圍。這裡，當 b-a < d-c 或 b-a == d-c 時 a < c 時，範圍 [a,b] 小於範圍 [c,d]。
因此，如果輸入類似於 [[4,10,15,25,26],[0,9,14,20],[5,18,24,30]]，則輸出將為 [14, 18]
為了解決這個問題，我們將遵循以下步驟：
minRange := ∞, maxRange := -∞, rangeSize := ∞, tempMinRange := ∞, tempMaxRange := -∞
n := nums 的大小
定義大小為 n 的指標陣列
建立一個優先順序佇列 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, ]
61 次檢視
