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 -
- minRange:=inf, maxRange:=-inf, rangeSize:=inf, tempMinRange:=inf, tempMaxRange:=-inf
- n:=kích thước của nums
- Xác định một con trỏ mảng có kích thước n
- tạo một hàng đợi ưu tiên pq
- để khởi tạo i:=0, khi i
- chèn {nums [i, 0], i} vào pq
- tempMaxRange:=tối đa tempMaxRange và nums [i, 0]
- Xác định một cặp temp:=top of pq
- xóa phần tử khỏi pq
- tempMinRange:=temp.first
- idx:=phần tử thứ hai của nhiệt độ
- nếu tempMaxRange - tempMinRange
- rangeSize:=tempMaxRange - tempMinRange
- minRange:=tempMinRange
- maxRange:=tempMaxRange
- Ra khỏi vòng lặp
- tempMaxRange:=tối đa tempMaxRange và nums [idx, con trỏ [idx]]
- chèn {nums [idx, pointers [idx]], idx} vào pq
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, ]