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 만들기
- 초기화 i의 경우:=0, i
- pq에 { nums[i, 0], i } 삽입
- tempMaxRange :=tempMaxRange 및 nums[i, 0]의 최대값
- 한 쌍의 temp 정의:=pq의 상단
- pq에서 요소 삭제
- tempMinRange :=temp.first
- idx :=temp의 두 번째 요소
- tempMaxRange - tempMinRange
- 범위 크기:=tempMaxRange - tempMinRange
- 최소 범위 :=tempMinRange
- maxRange :=tempMaxRange
- 루프에서 빠져나오기
- tempMaxRange :=tempMaxRange 및 nums[idx, pointers[idx]]의 최대값
- pq에 { nums[idx, pointers[idx]], idx } 삽입
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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, ]