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