ડેટા સ્ટ્રીમથી સરેરાશ શોધો  


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન ByteDance ફેસબુક ગોલ્ડમૅન સૅશ Google માઈક્રોસોફ્ટ Nvidia ઓરેકલ Salesforce Twitter વીએમવેર
ડિઝાઇન .ગલો

ડેટા સ્ટ્રીમ સમસ્યામાંથી મેડિયન શોધો, અમે આપ્યું છે કે ડેટા સ્ટ્રીમથી પૂર્ણાંકો વાંચવામાં આવે છે. પહેલા પૂર્ણાંકથી અંતિમ પૂર્ણાંક સુધી શરૂ કરીને અત્યાર સુધી વાંચેલા બધા તત્વોના મધ્યને શોધો.

ઉદાહરણ  

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

મધ્યસ્થ: તેને ડેટા સેટમાં તત્વ તરીકે વ્યાખ્યાયિત કરી શકાય છે જે ડેટા નમૂનાના ઉચ્ચ ભાગને નીચલા અર્ધથી અલગ કરે છે. જ્યારે ઇનપુટ ડેટાનું કદ વિચિત્ર હોય છે, ત્યારે ઇનપુટ ડેટાનો સરેરાશ એ સortedર્ટ કરેલા ઇનપુટ ડેટાનો મધ્યમ તત્વ હોય છે. જ્યારે ઇનપુટ ડેટાનું કદ બરાબર હોય, ત્યારે સરેરાશ સortedર્ટ કરેલા ઇનપુટ ડેટામાં સરેરાશ મધ્યમ બે ઘટકો હોય છે.

સોલ્યુશનના પ્રકારો  

  1. નિવેશ સ sortર્ટ
  2. હિપ ડેટા સ્ટ્રક્ચરનો ઉપયોગ કરીને
  3. ઓર્ડર આપેલ મલ્ટિસેટ ડેટા સ્ટ્રક્ચરનો ઉપયોગ (બહુવિધ સમાન મૂલ્યો સાથે વૃક્ષ સેટ)

નિવેશ સortર્ટ

પ્રવાહમાંથી પહેલાથી પ્રાપ્ત થયેલા ઘટકોને સ sર્ટર્ડમાં રાખવાનો વિચાર છે. એકવાર અમને પ્રવાહમાંથી કોઈ નવું તત્વ પ્રાપ્ત થાય છે, તે પછી અમે સ obtainedર્ટ કરેલા ક્રમમાં તે યોગ્ય સ્થાન શોધી કા .ીએ છીએ અને નવી પ્રાપ્ત કરેલ સortedર્ટ orderર્ડરનો સરેરાશ શોધવા માટે નવા તત્વને યોગ્ય સ્થાને મૂકીએ છીએ. આ અમે શું કરીએ છીએ નિવેશ સ sortર્ટ અલ્ગોરિધમ.

આ પણ જુઓ
રેન્જ ન્યૂનતમ ક્વેરી (સ્ક્વેર રુટ વિઘટન અને છૂટાછવાયા કોષ્ટક)

સી ++ પ્રોગ્રામ માટે ડેટા સ્ટ્રીમથી સરેરાશ શોધો

#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), રેખીય સ sortર્ટિંગ (નિવેશ સ sortર્ટ) એરે ટ્રversવર્સલ સાથે માળાવાળું છે.
  2. અવકાશ જટિલતા: A (n) = O (1), પ્રવાહ સ્ટોર કરવા સિવાય કોઈ જગ્યા લેવામાં આવતી નથી.
આ પણ જુઓ
બહિર્મુખ હલ એલ્ગોરિધમ

હિપ ડેટા સ્ટ્રક્ચરનો ઉપયોગ

અનુક્રમે નીચેના અડધા અને ઉચ્ચ ભાગના તત્વોને સંગ્રહિત કરવા માટે મહત્તમ heગલો અને મીન-હીપ ડેટા સ્ટ્રક્ચરનો ઉપયોગ કરવાનો વિચાર છે. બંને .ગલાઓના મૂળમૂલ્યોનો ઉપયોગ કરીને, આપણે પૂર્ણાંકોના વહેતા પ્રવાહના મધ્યની ગણતરી કરવામાં સક્ષમ છીએ. આ અલ્ગોરિધમનો નીચેની રીતે અમલમાં મૂકવામાં આવે છે:

અલ્ગોરિધમ

  1. બે .ગલા બનાવો. એક મહત્તમ apગલો (મહત્તમ) નીચલા અડધા અને એક મિનિટના ofગલાના ઘટકો જાળવવા માટે (minheap) કોઈપણ સમયે ઉચ્ચ અર્ધના તત્વોને જાળવવા માટે.
  2. શરૂઆતમાં, સરેરાશનું મૂલ્ય 0 છે.
  3. પ્રવાહમાંથી પ્રાપ્ત વર્તમાન તત્વ માટે તેને કોઈપણ apગલામાં દાખલ કરો અને નીચેના નિવેદનોમાં વર્ણવેલ મધ્યની ગણતરી કરો.
  4. જો બંને apગલાઓના કદ સમાન હોય.
    • જો વર્તમાન તત્વ સરેરાશ મૂલ્ય કરતા વધારે હોય, તો તેને ઓછામાં ઓછા apગલામાં દાખલ કરો minheap નવા સરેરાશ તરીકે.
    • અન્યથા જો વર્તમાન તત્વ સરેરાશ મૂલ્ય કરતા ઓછું હોય, તો તેને મહત્તમ apગલામાં દાખલ કરો મહત્તમ નવા સરેરાશ તરીકે.
  5. બીજું જો કદ મહત્તમ કરતાં વધારે છે minheap :
    • જો વર્તમાન તત્વ સરેરાશ કરતા વધારે હોય, તો વર્તમાન તત્વ દાખલ કરો minheap.
    • અન્યથા જો વર્તમાન તત્વ સરેરાશ કરતા ઓછું હોય, તો તેના મૂળને પ popપ કરો મહત્તમ અને તેને મિનિટમાં શામેલ કરોheap. હવે વર્તમાન તત્વ દાખલ કરો મહત્તમ.
    • ની મૂળની સરેરાશ તરીકે સરેરાશ ગણતરી કરો minheap અને મહત્તમ.
  6. બીજું જો કદ મહત્તમ કરતાં ઓછું છે minheap :
    • જો વર્તમાન તત્વ સરેરાશ કરતા ઓછું હોય, તો વર્તમાન તત્વ તેમાં દાખલ કરો મહત્તમ.
    • અન્યથા જો વર્તમાન તત્વ સરેરાશ કરતા વધારે હોય, તો મિનહેપની ટોચ પ popપ કરો અને તેમાં દાખલ કરો મહત્તમ. હવે વર્તમાન તત્વ દાખલ કરો minheap.
    • ની મૂળની સરેરાશ તરીકે સરેરાશ ગણતરી કરો minheap અને મહત્તમ.

ડેટા સ્ટ્રીમથી સરેરાશ શોધોપિન ડેટા સ્ટ્રીમથી સરેરાશ શોધોપિન

 

આ પણ જુઓ
એક એરે શફલ

ડેટા સ્ટ્રીમથી મેડિયન શોધો માટે સી ++ પ્રોગ્રામ

#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. સમયની જટિલતા: ટી તત્વોના ofગલાની રચના માટે, ટી (એન) = ઓ (નાલોગન).
  2. અવકાશ જટિલતા: એ (એન) = ઓ (એન), સ્ટ્રીમ મૂલ્યો apગલામાં સંગ્રહિત થાય છે.
આ પણ જુઓ
સિક્કો ચેન્જ સમસ્યા

ઓર્ડર થયેલ મલ્ટિસેટ ડેટા સ્ટ્રક્ચરનો ઉપયોગ

અમે બે ઇરેટર ટાઇપ પોઇન્ટર સાથે મલ્ટિસેટ ડેટા સ્ટ્રક્ચર્સનો ઉપયોગ કરીએ છીએ બાકી અને અધિકાર, અને જ્યારે આપણે મલ્ટિસેટમાં કોઈ તત્વ દાખલ કરીએ છીએ, ત્યારે અમે આ નિર્દેશકોને સ sર્ટ કરેલા પ્રવાહના મધ્યમ તત્વ પર નિર્દેશિત કરવા માટે સંશોધિત કરીએ છીએ. આ નીચે પ્રમાણે કરવામાં આવે છે:

અલ્ગોરિધમ

  1. સortedર્ટ થયેલ મલ્ટિસેટ વેરીએબલ બનાવે છે.
  2. ડાબી અને જમણી સisર્ટ કરેલ મલ્ટિસેટ માટે બે ઇટરેટર બનાવો.
  3. પ્રવાહના દરેક તત્વ (અમારા વર્તમાન તત્વ) પર પ્રક્રિયા કરો અને સ elementર્ટમાં તત્વ શામેલ કરો.
  4. જો સ sર્ટ કરેલું કદ 1 છે (પ્રથમ તત્વ શામેલ કરવામાં આવે છે), તો સ ofર્ટ કરેલા પ્રથમ તત્વ તરફ ડાબે અને જમણે પોઇન્ટ કરો.
  5. બીજું
    1. જો કદ (સortedર્ટ કરેલું) બરાબર છે, એટલે કે મધ્યમાં સમાન તત્વનો ડાબો અને જમણો પોઇન્ટ.
      • જો વર્તમાન તત્વ જમણા દ્વારા નિર્દેશિત તત્વ કરતા વધારે છે, તો આગળના તત્વની આગળ જાવ.
      • અન્યથા જો વર્તમાન તત્વ જમણા દ્વારા નિર્દેશિત તત્વ કરતા ઓછું હોય, તો પાછલા તત્વ પર ડાબેથી પાછા ફરો.
    2. જો કદ (સortedર્ટ) વિચિત્ર હોય, એટલે કે એરેની વચ્ચે ડાબી અને જમણી બિંદુ સળંગ તત્વો તરફ.
      • જો વર્તમાન તત્વ જમણા દ્વારા નિર્દેશિત તત્વ કરતા વધારે છે, તો આગળના તત્વથી ડાબી તરફ આગળ વધો.
      • અન્યથા જો વર્તમાન તત્વ ડાબી બાજુ દ્વારા નિર્દેશિત તત્વ કરતા ઓછું હોય, તો પાછલા તત્વની જમણી બાજુ ખસેડો.
      • અન્યથા જો વર્તમાન તત્વ ડાબેથી મોટું અને જમણે કરતા ઓછું હોય, તો ડાબી તરફ અને જમણેથી પાછળ તરફ ખસેડો.
  6. નીચેનાનો ઉપયોગ કરીને દરેક પગલા પર સરેરાશની ગણતરી કરો: સરેરાશ = (ડાબે + જમણે) / 2.

ડેટા સ્ટ્રીમથી સરેરાશ શોધોપિન

ડેટા સ્ટ્રીમથી મેડિયન શોધો માટે સી ++ પ્રોગ્રામ

#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. સમયની જટિલતા: ટી તત્વોના મલ્ટિસેટની રચના માટે, ટી (એન) = ઓ (નાલોગન).
  2. અવકાશ જટિલતા: એ (એન) = ઓ (એન), સ્ટ્રીમ મૂલ્યો સમૂહમાં સંગ્રહિત થાય છે.
આ પણ જુઓ
કેએમપી એલ્ગોરિધમ

સંદર્ભ