Giả sử chúng ta có k danh sách các số nguyên đã được sắp xếp. Chúng ta phải tìm kiếm phạm vi nhỏ nhất bao gồm ít nhất một số từ mỗi danh sách k. Ở đây phạm vi [a, b] nhỏ hơn phạm vi [c, d] khi b-a
Vì vậy, nếu đầu vào là [[4,10,15,25,26], [0,9,14,20], [5,18,24,30]], thì đầu ra sẽ là [14, 18]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
}
Đầu vào
{{4,10,15,25,26},{0,9,14,20},{5,18,24,30}};
Đầu ra
[14, 18, ]