C++의 k 목록에서 요소를 포함하는 가장 작은 범위 찾기

k개의 서로 다른 목록이 있다고 가정합니다. 요소가 정렬됩니다. k개의 서로 다른 목록 각각에서 적어도 하나의 숫자를 포함하는 가장 작은 범위를 검색해야 합니다. 여기서 범위 [a,b]는 b-a

따라서 입력이 [[4,10,15,25,26],[0,9,14,20],[5,18,24,30]]과 같으면 출력은 [14, 18]이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• minRange :=inf, maxRange :=-inf, rangeSize :=inf, tempMinRange :=inf, tempMaxRange :=-inf

• n :=숫자 크기

• n

  크기의 배열 포인터 정의

• 우선순위 큐를 pq로 만듭니다.

• initialize i :=0의 경우, i

  • pq에 { nums[i, 0], i } 삽입

  • tempMaxRange :=tempMaxRange 및 nums[i, 0]

    의 최대값

• 1이 0이 아닌 동안 −

  • 한 쌍의 온도 정의 :=pq의 상단

  • pq에서 요소 삭제

  • tempMinRange :=temp.first

  • idx :=temp의 두 번째 요소

  • tempMaxRange - tempMinRange

    • rangeSize :=tempMaxRange - tempMinRange

    • minRange :=tempMinRange

    • maxRange :=tempMaxRange

  • (1만큼 포인터[idx] 증가)

  • 포인터[idx]가 nums[idx]의 크기와 같으면 -

    • 루프에서 나오세요

  • 그렇지 않으면

    • tempMaxRange :=tempMaxRange 및 nums[idx, pointers[idx]]

      의 최대값

    • pq에 { nums[idx, pointers[idx]], idx } 삽입

• 크기가 2인 배열을 정의하십시오.

• ans[0] :=minRange, ans[1] :=maxRange

• 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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