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

C++ में डेटा स्ट्रीम से मेडियन ढूंढें


मान लीजिए हमारे पास एक डेटा स्ट्रीम है, उस स्ट्रीम में कुछ डेटा तत्व आ सकते हैं और जुड़ सकते हैं, हमें एक सिस्टम बनाना है, जो डेटा से मेडियन ढूंढने में मदद करेगा। जैसा कि हम जानते हैं कि मेडियन एक क्रमबद्ध सूची का मध्य डेटा है, यदि सूची की लंबाई विषम है, तो हम सीधे मेडियन प्राप्त कर सकते हैं, अन्यथा मध्य के दो तत्व लें, फिर औसत ढूंढें। तो दो विधियां होंगी, addNum() और findMedian(), इन दो विधियों का उपयोग संख्याओं को स्ट्रीम में जोड़ने के लिए, और सभी जोड़ी गई संख्याओं का मेडियन ढूंढने के लिए किया जाएगा

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

  • प्राथमिकता कतार left और right परिभाषित करें

  • addNum विधि परिभाषित करें, जो संख्या को इनपुट के रूप में लेगी -

  • यदि left खाली है या num < left का शीर्ष तत्व, तो,

    • num को left में डालें

  • अन्यथा

    • num को right में डालें

  • यदि left का आकार < right का आकार, तो,

    • temp := right का शीर्ष तत्व

    • right से आइटम हटाएं

    • temp को left में डालें

  • यदि left का आकार - right का आकार > 1, तो,

    • temp := left का शीर्ष तत्व

    • left से आइटम हटाएं

    • temp को right में डालें

  • findMedian() विधि परिभाषित करें, यह निम्नानुसार कार्य करेगी -

    • यदि left का आकार > right का आकार तो left का शीर्ष लौटाएं, अन्यथा (left का शीर्ष + right का शीर्ष)/2

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h> using namespace std; typedef double lli; class MedianFinder {    priority_queue <int> left;    priority_queue <int, vector <int>, greater<int>> right;    public:    void addNum(int num) {       if(left.empty() || num<left.top()){          left.push(num);       }else right.push(num);       if(left.size()<right.size()){          lli temp = right.top();          right.pop();          left.push(temp);       }       if(left.size()-right.size()>1){          lli temp = left.top();          left.pop();          right.push(temp);       }    }    double findMedian() {       return       left.size()>right.size()?left.top():(left.top()+right.top())*0.5;    } }; main(){    MedianFinder ob;    ob.addNum(10);    ob.addNum(15);    cout << ob.findMedian() << endl;    ob.addNum(25);    ob.addNum(30);    cout << ob.findMedian() << endl;    ob.addNum(40);    cout << ob.findMedian(); }

इनपुट

addNum(10); addNum(15); findMedian(); addNum(25); addNum(30); findMedian(); addNum(40); findMedian();

आउटपुट

12.5 20 25

  1. C++ में बाइनरी ट्री में दी गई कुंजी का अगला दायां नोड ढूंढना C++ में बाइनरी ट्री में दी गई कुंजी का अगला दायां नोड ढूंढना

    इस समस्या में, हमें एक बाइनरी ट्री BT और एक कुंजी मान दिया जाता है। हमारा कार्य दी गई कुंजी का अगला दायां नोड ढूंढना है।बाइनरी ट्री डेटा स्टोरेज उद्देश्यों के लिए उपयोग की जाने वाली एक विशेष डेटा संरचना है।आइए एक उदाहरण से समस्या को समझते हैं,इनपुटkey = 4आउटपुट5व्याख्यानोड 4 के बगल में स्थित तत्व 5

  1. C++ में बाइनरी ट्री का बॉटम लेफ्ट मान C++ में बाइनरी ट्री का बॉटम लेफ्ट मान

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें ट्री की अंतिम पंक्ति (सबसे गहरे लेवल) का सबसे बायाँ मान ढूंढना है। उदाहरण: ट्री [3,5,1,6,2,0,8,null,null,7,4] के लिए अंतिम पंक्ति [7,4] है, इसलिए बॉटम लेफ्ट मान 7 है। DFS + गहराई ट्रैकिंग दो वेरिएबल्स ans और maxLevel (प्रारंभ में -1) रखें। रिकर्सिव sol

  1. C++ में बाइनरी ट्री के सभी लीफ नोड्स को दाएं से बाएं प्रिंट करना C++ में बाइनरी ट्री के सभी लीफ नोड्स को दाएं से बाएं प्रिंट करना

    इस समस्या में, हमें एक बाइनरी ट्री दी गई है और हमें बाइनरी ट्री के सभी लीफ नोड्स को दाएं से बाएं प्रिंट करना है। उदाहरण इनपुट - आउटपुट - 7 4 1 इस समस्या को हल करने के लिए, हमें बाइनरी ट्री को पार करना होगा। यह ट्रैवर्सल दो तरीकों से किया जा सकता है - प्रीऑर्डर ट्रैवर्सल यह ट्रैवर्सल रिकर्सन का