Giả sử chúng ta có k danh sách khác nhau. Các phần tử đượ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 khác nhau. Ở đâ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 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 của tempMaxRange và nums [i, 0]
-
-
trong khi 1 là khác 0, do -
-
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 tạm thời
-
nếu tempMaxRange - tempMinRange
-
rangeSize:=tempMaxRange - tempMinRange
-
minRange:=tempMinRange
-
maxRange:=tempMaxRange
-
-
(tăng con trỏ [idx] lên 1)
-
nếu con trỏ [idx] giống với kích thước của nums [idx], thì -
-
Ra khỏi vòng lặp
-
-
Nếu không
-
tempMaxRange:=tối đa của tempMaxRange và nums [idx, con trỏ [idx]]
-
chèn {nums [idx, pointers [idx]], idx} vào pq
-
-
-
Xác định ans mảng có kích thước 2
-
ans [0]:=minRange, ans [1]:=maxRange
-
trả lại ans
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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, ]