डेटा स्ट्रीम से मेडियन का पता लगाएं


कठिनाई स्तर कठिन
में अक्सर पूछा वीरांगना सेब ByteDance Facebook गोल्डमैन सैक्स गूगल माइक्रोसॉफ्ट Nvidia ओरेकल Salesforce Twitter VMware
डिज़ाइन ढेर

डेटा स्ट्रीम समस्या से मेडियन का पता लगाने में, हमने दिया है कि पूर्णांकों को डेटा स्ट्रीम से पढ़ा जा रहा है। पहले पूर्णांक से अंतिम पूर्णांक तक शुरू होने वाले अब तक पढ़े गए सभी तत्वों के मध्य का पता लगाएं।

उदाहरण

Input 1: stream[ ] = {3,10,5,20,7,6}
Output : 3    6.5     5     7.5     7     6.5

Input 2: stream[ ] = {20,1,11,19,21,17,6}
Output : 20     10.5     11     15     19     18     17

मंझला: इसे डेटा सेट में उस तत्व के रूप में परिभाषित किया जा सकता है जो डेटा नमूने के उच्च आधे हिस्से को निचले आधे हिस्से से अलग करता है। जब इनपुट डेटा का आकार विषम होता है, तो इनपुट डेटा का माध्य हल किए गए इनपुट डेटा का मध्य तत्व होता है। जब इनपुट डेटा का आकार समान होता है, तो औसत इनपुट डेटा में औसत मध्य दो तत्व होते हैं।

समाधान के प्रकार

  1. सम्मिलन सॉर्ट
  2. ढेर डेटा संरचना का उपयोग करना
  3. आदेशित मल्टीसेट डेटा संरचना का उपयोग करना (कई समान मूल्यों के साथ ट्री सेट)

सम्मिलन सॉर्ट

विचार धारा में पहले से प्राप्त तत्वों को क्रमबद्ध क्रम में रखने का है। एक बार जब हम धारा से एक नया तत्व प्राप्त करते हैं, तो हम पाते हैं कि यह क्रमबद्ध क्रम में सही जगह है और नए तत्व को नए स्थान पर क्रमबद्ध क्रम के मध्य का पता लगाने के लिए सही जगह पर रखें। यही हम करते हैं सम्मिलन सॉर्ट कलन विधि।

C ++ प्रोग्राम के लिए डेटा स्ट्रीम से मेडियन का पता लगाएं

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// placing the last element recieved at it's correct position in a sorted vector
void insertionSort(vector <int>& sorted)
{
    int last_inserted = sorted.size()-1;
    while(last_inserted > 0 && sorted[last_inserted] < sorted[last_inserted-1])
    {
        swap(sorted[last_inserted-1],sorted[last_inserted]);
        last_inserted--;
    }
}

// prints median out of a given stream of integer values
void printMedian(vector <int> stream)
{
    // vector to store values in sorted order
    // for printing of the median value
    vector <int> sorted;
    
    for(int i=0;i<stream.size();i++)
    {
        sorted.push_back(stream[i]);
        
        if(sorted.size() == 1)
        cout<<sorted[0]<<"\t";
        
        else
        {
            // sort the sorted vector
            insertionSort(sorted);
            
            // if number of elements recieved is odd
            // middle element is the median
            if(sorted.size()%2 == 1)
            {
                int mid = sorted.size()/2;
                
                cout<<sorted[mid]<<"\t";
            }
            // if size is even
            // average of middle two elements is the median
            else
            {
                int mid1 = (sorted.size()-1)/2;
                int mid2 = sorted.size()/2;
                
                cout<<(float)(sorted[mid1]+sorted[mid2])/2<<"\t";
            }
        }
    }
}

// main function to implement median of stream of integers
int main()
{
    vector <int> stream  = {3,10,5,20,7,6};
    printMedian(stream);
    return 0;
}
3	6.5	5	7.5	7	6.5

डेटा स्ट्रीम से मेडियन के लिए जावा प्रोग्राम

import java.io.*;
import java.util.*;

class tutorialcup
{
    // placing the last element recieved at it's correct position in a sorted vector
    static void insertionSort(ArrayList <Integer> sorted)
    {
        int last_inserted = sorted.size()-1;
        while(last_inserted > 0 && sorted.get(last_inserted) < sorted.get(last_inserted-1))
        {
            int temp = sorted.get(last_inserted-1);
            sorted.set(last_inserted-1,sorted.get(last_inserted));
            sorted.set(last_inserted,temp);
            
            last_inserted--;
        }
    }
    
    // prints median out of a given stream of integer values
    static void printMedian(ArrayList <Integer> stream)
    {
        // vector to store values in sorted order
        // for printing of the median value
        ArrayList <Integer> sorted = new ArrayList <Integer>();
        
        for(int i=0;i<stream.size();i++)
        {
            sorted.add(stream.get(i));
            
            if(sorted.size() == 1)
            System.out.print(sorted.get(0)+"\t");
            else
            {
                // sort the sorted vector
                insertionSort(sorted);
                
                // if number of elements recieved is odd
                // middle element is the median
                if(sorted.size() %2 == 1)
                {
                    int mid = sorted.size()/2;
                    System.out.print(sorted.get(mid)+"\t");
                }
                
                // if size is even
                // average of middle two elements is the median
                else
                {
                    int mid1 = (sorted.size()-1)/2;
                    int mid2 = sorted.size()/2;
                    
                    float median = (float)(sorted.get(mid1)+sorted.get(mid2))/2;
                    
                    System.out.print(median + "\t");
                }
            }
        }
    }
    // main function to implement median of stream of integers
    public static void main (String[] args) 
    {
        ArrayList <Integer> stream = new ArrayList <Integer> (Arrays.asList(3,10,5,20,7,6));
        printMedian(stream);
    }
}
3	6.5	5	7.5	7	6.5

जटिलता विश्लेषण

  1. समय जटिलता: टी (एन) = ओ (एन)2), रैखिक छँटाई (प्रविष्टि प्रकार) सरणी ट्रैवर्सल के साथ नेस्टेड है।
  2. अंतरिक्ष जटिलता: A (n) = O (1), धारा को संचय करने के अलावा कोई स्थान नहीं लिया जाता है।

हीप डेटा संरचना का उपयोग करना

यह विचार है कि क्रमशः निचले आधे और उच्च आधे के तत्वों को संग्रहीत करने के लिए अधिकतम ढेर और न्यूनतम-ढेर डेटा संरचना का उपयोग करना है। दोनों ढेर के मूल मूल्यों का उपयोग करके, हम पूर्णांकों की रनिंग स्ट्रीम के माध्य की गणना करने में सक्षम हैं। कलन विधि निम्नलिखित तरीकों से कार्यान्वित किया जाता है:

कलन विधि

  1. दो ढेर बनाएँ। एक अधिकतम ढेर (अधिकतम) निचले आधे और एक मिनट के ढेर के तत्वों को बनाए रखने के लिए (खान में काम करनेवाला) किसी भी समय उच्चतर आधे के तत्वों को बनाए रखने के लिए।
  2. प्रारंभ में, माध्य का मान 0 होता है।
  3. धारा से प्राप्त वर्तमान तत्व के लिए इसे किसी भी ढेर में डालें और निम्नलिखित कथनों में वर्णित माध्यिका की गणना करें।
  4. यदि दोनों ढेर का आकार समान है।
    • यदि वर्तमान तत्व माध्य मान से अधिक है, तो इसे न्यूनतम heap.return की जड़ में डालें खान में काम करनेवाला नए मंझले के रूप में।
    • यदि वर्तमान तत्व माध्य मान से कम है, तो इसे अधिकतम heap.return की जड़ में डालें अधिकतम नए मंझले के रूप में।
  5. और अगर आकार अधिकतम से अधिक है खान में काम करनेवाला :
    • यदि वर्तमान तत्व माध्यिका से अधिक है, तो वर्तमान तत्व को अंदर डालें खान में काम करनेवाला।
    • यदि वर्तमान तत्व माध्यिका से कम है, तो मूल को पॉप करें अधिकतम और इसे मिनट में डालेंheap। अब वर्तमान तत्व डालें अधिकतम
    • की जड़ के औसत के रूप में माध्यिका की गणना करें खान में काम करनेवाला और अधिकतम
  6. और अगर आकार अधिकतम से कम है खान में काम करनेवाला :
    • यदि वर्तमान तत्व माध्यिका से कम है, तो वर्तमान तत्व को डालें अधिकतम
    • और यदि वर्तमान तत्व माध्यिका से अधिक है, तो मिनिएप के शीर्ष को पॉप करें और इसे डालें अधिकतम अब वर्तमान तत्व डालें खान में काम करनेवाला।
    • की जड़ के औसत के रूप में माध्यिका की गणना करें खान में काम करनेवाला और अधिकतम

डेटा स्ट्रीम से मेडियन का पता लगाएं डेटा स्ट्रीम से मेडियन का पता लगाएं

 

डेटा स्ट्रीम से मेडियन खोजने के लिए C ++ प्रोग्राम

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// prints median out of a given stream of integer values
void printMedian(vector <int> stream)
{
    // initial value of median is 0
    float median = 0;
    // to store the lower half of sorted stream
    priority_queue <int> maxheap;
    // to store the upper half of sorted stream
    priority_queue <int,vector <int>,greater <int> > minheap;
    
    // process the stream of values    
    for(int i=0;i<stream.size();i++)
    {
        int curr = stream[i];
        
        // if size of both the heap is same
        if(maxheap.size() == minheap.size()) 
        {
            if(curr >= median)
            {
                minheap.push(curr);
                median = minheap.top();
            }
            else
            {
                maxheap.push(curr);
                median = maxheap.top();
            }   
        }
        
        // if size of heaps are different
        // after inserting the element from the stream
        // size of both heap becomes equal 
        // median is average of roots of both the heaps
        else
        {
            if(maxheap.size() > minheap.size())
            {
                if(curr > median)
                minheap.push(curr);
                else
                {
                    minheap.push(maxheap.top());
                    maxheap.pop();
                    maxheap.push(curr);
                }
            }
            
            else
            {
                if(curr < median)
                maxheap.push(curr);
                else
                {
                    maxheap.push(minheap.top());
                    minheap.pop();
                    minheap.push(curr);
                }
            }
            
            median = (float)(minheap.top()+maxheap.top())/2;
        }
        
        cout<<median<<"\t";
    }
}

// main function to implement median of stream of integers
int main()
{
    vector <int> stream  = {3,10,5,20,7,6};
    printMedian(stream);
    return 0;
}
3	6.5	5	7.5	7	6.5

डेटा स्ट्रीम से मेडियन के लिए जावा प्रोग्राम

import java.io.*;
import java.util.*;

class tutorialcup
{
    // prints median out of a given stream of integer values
    static void printMedian(ArrayList <Integer> stream)
    {
        // initial value of median is 0
        float median = 0;
        // to store the lower half of sorted stream
        PriorityQueue <Integer> minheap = new PriorityQueue<Integer>();
        // to store the upper half of sorted stream
        PriorityQueue <Integer> maxheap = new PriorityQueue<Integer>(Collections.reverseOrder());
        
        // process the stream of values    
        for(int i=0;i<stream.size();i++)
        {
            int curr = stream.get(i);
            
            // if size of both the heap is same
            if(maxheap.size() == minheap.size()) 
            {
                if(curr >= median)
                {
                    minheap.add(curr);
                    median = minheap.peek();
                }
                else
                {
                    maxheap.add(curr);
                    median = maxheap.peek();
                }   
            }
            
            // if size of heaps are different
            // after inserting the element from the stream
            // size of both heap becomes equal 
            // median is average of roots of both the heaps
            else
            {
                if(maxheap.size() > minheap.size())
                {
                    if(curr > median)
                    minheap.add(curr);
                    else
                    {
                        minheap.add(maxheap.remove());
                        maxheap.add(curr);
                    }
                }
                
                else
                {
                    if(curr < median)
                    maxheap.add(curr);
                    else
                    {
                        maxheap.add(minheap.remove());
                        minheap.add(curr);
                    }
                }
                
                median = (float)(minheap.peek()+maxheap.peek())/2;
            }
            
            System.out.print(median+"\t");
        }
    }
    // main function to implement median of stream of integers
    public static void main (String[] args) 
    {
        ArrayList <Integer> stream = new ArrayList <Integer> (Arrays.asList(3,10,5,20,7,6));
        printMedian(stream);
    }
}
3	6.5	5	7.5	7	6.5

जटिलता विश्लेषण

  1. समय की जटिलता: टी तत्वों के ढेर के गठन के लिए टी (एन) = हे (क्लॉग)।
  2. अंतरिक्ष जटिलता: A (n) = O (n), धारा मान ढेर में जमा होते हैं।

आदेशित मल्टीसेट डेटा संरचना का उपयोग करना

हम दो पुनरावृत्ति प्रकार बिंदुओं के साथ एक मल्टीसेट डेटा संरचनाओं का उपयोग करते हैं बाएं और सही, जब और जब हम मल्टीसेट में एक तत्व सम्मिलित करते हैं, तो हम इन बिंदुओं को क्रमबद्ध धारा के मध्य तत्व को इंगित करने के लिए संशोधित करते हैं। यह नीचे दिया गया है:

कलन विधि

  1. एक मल्टीसेट वेरिएबल क्रमित करता है।
  2. बाएँ और दाएँ सॉर्ट किए गए मल्टीसेट के लिए दो पुनरावृत्तियों बनाएँ।
  3. धारा के प्रत्येक तत्व (हमारे वर्तमान तत्व) को संसाधित करें और तत्व को सॉर्ट में डालें।
  4. यदि सॉर्ट किए गए का आकार 1 है (पहला तत्व डाला गया है), सॉर्ट किए गए पहले तत्व पर बाएं और दाएं बिंदु।
  5. अन्य
    1. यदि आकार (छांटा गया) सम है, तो बीच में एक ही तत्व के लिए बाएँ और दाएँ बिंदु।
      • यदि वर्तमान तत्व दाईं ओर इंगित किए गए तत्व से अधिक है, तो अगले तत्व के लिए अग्रिम।
      • वरना यदि वर्तमान तत्व दाईं ओर इंगित किए गए तत्व से कम है, तो पिछले तत्व पर वापस जाएं।
    2. अगर आकार (छांटा गया) विषम है, तो सरणी के बीच में लगातार तत्वों को बाएं और दाएं बिंदु।
      • यदि वर्तमान तत्व दाईं ओर इंगित किए गए तत्व से अधिक है, तो अगले तत्व के लिए अग्रिम छोड़ दिया गया है।
      • वरना यदि वर्तमान तत्व बाईं ओर इंगित किए गए तत्व से कम है, तो पिछले तत्व पर दाएं जाएं।
      • वरना यदि वर्तमान तत्व बाएं से अधिक है और दाएं से कम है, तो बाएं से बाएं और पीछे से दाएं आगे बढ़ें।
  6. निम्नलिखित का उपयोग करके हर कदम पर माध्य की गणना करें: माध्य = (बाएं + दाएं) / 2।

डेटा स्ट्रीम से मेडियन का पता लगाएं

डेटा स्ट्रीम से मेडियन खोजने के लिए C ++ प्रोग्राम

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// prints median out of a given stream of integer values
void printMedian(vector <int> stream)
{
    // declare multiset to store sorted order
    multiset <int> sorted;
    // declare iterators of multiset type
    multiset<int>::iterator left,right;
    // initialize median
    float median = 0;
    // process the stream
    for(int i=0;i<stream.size();i++)
    {
        // insert each element into multiset
        sorted.insert(stream[i]);
        
        // for first element inserted
        // initiate left and right pointers
        if(sorted.size() == 1)
        {
            left = sorted.begin();
            right = sorted.begin();
            median = *left;
        }
        // for subsequent elements inserted
        else
        {
            // if size of multiset is even
            if(sorted.size()%2 == 0)
            {
                if(stream[i] >= *right)
                right++;
                else
                left--;
            }
            // if size of multiset is odd
            else
            {
                if(stream[i] >= *right)
                left++;
                else if(stream[i] <= *left)
                right--;
                else
                {
                    left++;
                    right--;
                }
            }
        }
        
        // median is average of elements pointed by left and right
        median = (float)(*left+*right)/2;
        
        cout<<median<<"\t";
    }
}

// main function to implement median of stream of integers
int main()
{
    vector <int> stream  = {3,10,5,20,7,6};
    printMedian(stream);
    return 0;
}
3	6.5	5	7.5	7	6.5

डेटा स्ट्रीम से मेडियन के लिए जावा प्रोग्राम

import java.io.*;
import java.util.*;
// library to access ordered multiset in java
import com.google.common.collect.TreeMultiset; 
class tutorialcup
{
    // prints median out of a given stream of integer values
    static void printMedian(ArrayList <Integer> stream)
    {
        // declare multiset to store sorted order
        TreeMultiset <Integer> sorted = TreeMultiset.create();
        // declare iterators of multiset type
        Iterator <Integer> left = sorted.iterator();
        Iterator <Integer> right = sorted.iterator();
        // initialize median
        float median = 0;
        // process the stream
        for(int i=0;i<stream.size();i++)
        {
            // insert each element into multiset
            sorted.add(stream.get(i));
            
            // for first element inserted
            // initiate left and right pointers
            if(sorted.size() == 1)
            {
                //left = sorted.begin();
                //right = sorted.begin();
                median = left.next();
            }
            // for subsequent elements inserted
            else
            {
                // if size of multiset is even
                if(sorted.size()%2 == 0)
                {
                    if(stream.get(i) >= right.next())
                    right.hasNext();
                    else
                    left.hasPrevious();
                }
                // if size of multiset is odd
                else
                {
                    if(stream.get(i) >= right.next())
                    left.hasNext();
                    else if(stream.get(i) <= left.next())
                    right.hasPrevious();
                    else
                    {
                        left.hasNext();
                        right.hasPrevious();
                    }
                }
            }
            
            // median is average of elements pointed by left and right
            median = (float)(left.next()+right.next())/2;
            System.out.print(median+"\t");
        }
    }
    // main function to implement median of stream of integers
    public static void main (String[] args) 
    {
        
        ArrayList <Integer> stream = new ArrayList <Integer> (Arrays.asList(3,10,5,20,7,6));
        printMedian(stream);
    }
}
3	6.5	5	7.5	7	6.5

जटिलता विश्लेषण

  1. समय की जटिलता: n (n) = O (nlogn), n तत्वों के मल्टीसेट के गठन के लिए।
  2. अंतरिक्ष जटिलता: ए (एन) = ओ (एन), धारा मान एक सेट में संग्रहीत किए जाते हैं।

संदर्भ