Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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] होगा।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

  • मिनरेंज := inf, मैक्सरेंज := -inf, रेंजसाइज := inf, टेम्पमिनरेंज := inf, टेम्पमैक्सरेंज := -inf
  • n := nums का आकार
  • आकार n का एक ऐरे पॉइंटर्स परिभाषित करें
  • एक प्रायोरिटी क्यू pq बनाएं
  • i := 0 से n-1 तक लूप करें:
    • { nums[i][0], i } को pq में डालें
    • टेम्पमैक्सरेंज := टेम्पमैक्सरेंज और nums[i][0] का अधिकतम
  • जब तक 1 शून्येतर है:
    • टेम्प := pq का शीर्ष परिभाषित करें
    • pq से तत्व हटाएं
    • टेम्पमिनरेंज := टेम्प.फर्स्ट
    • इंडेक्स := टेम्प.सेकंड
    • यदि टेम्पमैक्सरेंज - टेम्पमिनरेंज < रेंजसाइज: रेंजसाइज, मिनरेंज, मैक्सरेंज अपडेट करें
    • पॉइंटर्स[इंडेक्स] बढ़ाएं
    • यदि पॉइंटर्स[इंडेक्स] nums[इंडेक्स] के आकार के बराबर है, तो लूप से बाहर निकलें
    • अन्यथा:
      • टेम्पमैक्सरेंज := टेम्पमैक्सरेंज और nums[इंडेक्स][पॉइंटर्स[इंडेक्स]] का अधिकतम
      • { nums[इंडेक्स][पॉइंटर्स[इंडेक्स]], इंडेक्स } को pq में डालें
  • आकार 2 का एक ऐरे ans परिभाषित करें
  • ans[0] := मिनरेंज, ans[1] := मैक्सरेंज
  • 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, ]

  1. - C++ में दी गई N रेंज के सभी तत्वों को कवर करने वाली रेंज ज्ञात करें

    मान लीजिए हमारे पास n रेंज हैं जिनमें L और R हैं। हमें 0-आधारित उस रेंज का सूचकांक जांचना या ढूंढना है जो अन्य सभी n-1 रेंज को कवर करती है। यदि ऐसी कोई रेंज नहीं है, तो -1 प्रदर्शित करें। उदाहरण के लिए, यदि L = [2, 4, 3, 1], और R = [4, 6, 7, 9], तो आउटपुट 3 है। इसका मतलब है कि तीसरे सूचकांक पर रेंज

  1. - C++ प्रोग्राम: क्रमबद्ध सरणी में दिए गए मान के k निकटतम तत्व ज्ञात करना

    मान लें हमारे पास कुछ तत्वों के साथ एक सरणी A है। हमारे पास दो अन्य मान X और k हैं। हमारा कार्य सरणी A से X के k निकटतम तत्वों की संख्या ज्ञात करना है। यदि तत्व X सरणी में मौजूद है, तो यह आउटपुट में नहीं दिखाया जाएगा। यदि A = [12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56] और X = 35, k = 4 है।

  1. - C++ प्रोग्राम: सरणी में सबसे छोटे मान की आवृत्ति ज्ञात करना

    यहां हम देखेंगे कि सरणी में सबसे छोटे तत्व की आवृत्ति कैसे ज्ञात करें। मान लें सरणी तत्व [5, 3, 6, 9, 3, 7, 5, 8, 3, 12, 3, 10] हैं, यहां सबसे छोटा तत्व 3 है, और इस तत्व की आवृत्ति 4 है। इसलिए आउटपुट 4 है। इसे हल करने के लिए हम सूची का सबसे छोटा तत्व ज्ञात करेंगे, फिर पहले नंबर की घटनाओं को गिनेंगे