C++ 中 K 個列表的最小範圍覆蓋元素

假設我們有 k 個排序整數列表。我們需要搜尋包含來自這 k 個列表中每個列表至少一個數字的最小範圍。這裡範圍 [a,b] 小於範圍 [c,d]，當 b-a < d-c 或 a < c 當 b-a == d-c 時。

因此，如果輸入類似於 [[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 := nums 的大小
  • 定義一個大小為 n 的陣列 pointers
  • 建立一個優先順序佇列 pq
  • 對於初始化 i := 0，當 i < n，更新（i 增加 1），執行 -
    • 將 { nums[i, 0], i } 插入 pq
    • tempMaxRange := tempMaxRange 和 nums[i, 0] 的最大值
  • 當 1 不為零時，執行 -
    • 定義一個對 temp := pq 的頂部
    • 從 pq 中刪除元素
    • tempMinRange := temp.first
    • idx := temp 的第二個元素
    • 如果 tempMaxRange - tempMinRange < rangeSize，則 -
      • rangeSize := tempMaxRange - tempMinRange
      • minRange := tempMinRange
      • maxRange := tempMaxRange
    • （pointers[idx] 增加 1）
    • 如果 pointers[idx] 與 nums[idx] 的大小相同，則 -
      • 退出迴圈
    • 否則
      • tempMaxRange := tempMaxRange 和 nums[idx, pointers[idx]] 的最大值
      • 將 { nums[idx, pointers[idx]], idx } 插入 pq
  • 定義一個大小為 2 的陣列 ans
  • ans[0] := minRange, ans[1] := maxRange
  • 返回 ans

讓我們看看以下實現以更好地理解 -

示例

 即時演示

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

更新於: 2020-06-01

212 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告