Tìm phạm vi nhỏ nhất chứa các phần tử từ k danh sách trong C ++

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, ]