Εύρεση μέσου από τη ροή δεδομένων  


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις αμαζόνα μήλο ByteDance Facebook Goldman Sachs Google Microsoft Nvidia μαντείο Salesforce Twitter VMware
Σχέδια Σωρός

Στο Find Median από το πρόβλημα ροής δεδομένων, έχουμε δώσει ότι οι ακέραιοι αριθμοί διαβάζονται από μια ροή δεδομένων. Βρείτε τη διάμεση τιμή όλων των στοιχείων που έχουν διαβαστεί μέχρι στιγμής ξεκινώντας από τον πρώτο ακέραιο έως τον τελευταίο ακέραιο.

Παράδειγμα  

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. χρησιμοποιώντας δομημένη δομή δεδομένων πολλαπλών συνόλων (Tree set με πολλές ίδιες τιμές)

Ταξινόμηση εισαγωγής

Η ιδέα είναι να διατηρήσετε τα στοιχεία που έχουν ήδη ληφθεί από τη ροή σε ταξινομημένη σειρά. Μόλις λάβουμε ένα νέο στοιχείο από τη ροή, βρίσκουμε το σωστό μέρος με την ταξινομημένη σειρά και τοποθετούμε το νέο στοιχείο στη σωστή θέση για να βρούμε τη μέση τιμή της νέας ταξινομημένης σειράς. Αυτό κάνουμε στο είδος εισαγωγής αλγόριθμος.

Βλέπε επίσης
Ελάχιστο ερώτημα εύρους (αποσύνθεση τετραγωνικής ρίζας και αραιός πίνακας)

Πρόγραμμα 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

Πρόγραμμα Java για εύρεση μέσου από τη ροή δεδομένων

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. Πολυπλοκότητα χρόνου: T (n) = O (n2), η γραμμική ταξινόμηση (είδος εισαγωγής) είναι ένθετη με εγκάρσια διάταξη
  2. Διαστημική πολυπλοκότητα: A (n) = O (1), δεν λαμβάνεται χώρος εκτός από την αποθήκευση της ροής.
Βλέπε επίσης
Αλγόριθμος κυρτού κύτους

Χρήση δομής δεδομένων σωρού

Η ιδέα είναι να χρησιμοποιήσετε τη δομή δεδομένων max heap και min-heap για να αποθηκεύσετε τα στοιχεία του κάτω μισού και του υψηλότερου μισού αντίστοιχα. Χρησιμοποιώντας τις ριζικές τιμές και των δύο σωρών, είμαστε σε θέση να υπολογίσουμε τη μέση τιμή της ροής των ακέραιων ρευμάτων. ο αλγόριθμος εφαρμόζεται με τους ακόλουθους τρόπους:

Αλγόριθμος

  1. Δημιουργήστε δύο σωρούς. Ένας μέγιστος σωρός (maxheap) για τη διατήρηση στοιχείων του κατώτερου μισού και του σωρού ενός λεπτού (ελάχιστο) για τη διατήρηση στοιχείων του υψηλότερου μισού ανά πάσα στιγμή.
  2. Αρχικά, η τιμή της μέσης τιμής είναι 0.
  3. Για το τρέχον στοιχείο που λαμβάνεται από τη ροή εισάγετε το σε έναν από τους σωρούς και υπολογίστε τη διάμεση τιμή που περιγράφεται στις ακόλουθες δηλώσεις.
  4. Εάν το μέγεθος και των δύο σωρών είναι το ίδιο.
    • εάν το τρέχον στοιχείο είναι μεγαλύτερο από τη μέση τιμή, εισαγάγετέ το στο ελάχιστο σωρό. γυρίστε τη ρίζα του ελάχιστο ως ο νέος διάμεσος.
    • αλλιώς εάν το τρέχον στοιχείο είναι μικρότερο από τη μέση τιμή, εισαγάγετέ το στο μέγιστο σωρό. γυρίστε τη ρίζα του maxheap ως ο νέος διάμεσος.
  5. αλλιώς Εάν το μέγεθος του maxheap είναι μεγαλύτερη από ό, τι ελάχιστο :
    • εάν το τρέχον στοιχείο είναι μεγαλύτερο από το διάμεσο, εισαγάγετε το τρέχον στοιχείο στο ελάχιστο.
    • αλλιώς εάν το τρέχον στοιχείο είναι μικρότερο από το διάμεσο, ανοίξτε τη ρίζα του maxheap και εισάγετε το σε ελάχιστοhεγω Τώρα εισαγάγετε το τρέχον στοιχείο στο maxheap.
    • υπολογίστε το διάμεσο ως μέσο όρο της ρίζας του ελάχιστο maxheap.
  6. αλλιώς Εάν το μέγεθος του maxheap είναι λιγότερο από ελάχιστο :
    • Εάν το τρέχον στοιχείο είναι μικρότερο από το διάμεσο, εισαγάγετε το τρέχον στοιχείο στο maxheap.
    • αλλιώς εάν το τρέχον στοιχείο είναι μεγαλύτερο από το διάμεσο, ανοίξτε την κορυφή του minheap και τοποθετήστε το στο maxheap. Τώρα εισαγάγετε το τρέχον στοιχείο στο ελάχιστο.
    • υπολογίστε το διάμεσο ως μέσο όρο της ρίζας του ελάχιστο maxheap.

Εύρεση μέσου από τη ροή δεδομένωνΚαρφώστε Εύρεση μέσου από τη ροή δεδομένωνΚαρφώστε

 

Βλέπε επίσης
Ανακατέψτε μια σειρά

Πρόγραμμα 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

Πρόγραμμα Java για εύρεση μέσου από τη ροή δεδομένων

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. Χρόνος πολυπλοκότητας: T (n) = O (nlogn), για σχηματισμό σωρού n στοιχείων.
  2. Διαστημική πολυπλοκότητα: A (n) = O (n), οι τιμές ροής αποθηκεύονται σε σωρό.
Βλέπε επίσης
Πρόβλημα αλλαγής νομισμάτων

Χρήση παραγγελίας δομής δεδομένων πολλαπλών συνόλων

Χρησιμοποιούμε δομές δεδομένων πολλαπλών συνόλων με δύο δείκτες τύπου επαναληπτικού αριστερά δεξιά, καθώς και όταν εισάγουμε ένα στοιχείο στο πολλαπλό σύνολο, τροποποιούμε αυτούς τους δείκτες ώστε να δείχνουν στο μεσαίο στοιχείο της ταξινομημένης ροής. Αυτό γίνεται όπως παρακάτω:

Αλγόριθμος

  1. δημιουργεί μια μεταβλητή πολλαπλών συνόλων ταξινομημένη.
  2. δημιουργήστε δύο επαναληπτικούς για ταξινομημένο πολλαπλό σύνολο αριστερά και δεξιά.
  3. Επεξεργαστείτε κάθε στοιχείο (το τρέχον στοιχείο μας) της ροής και εισαγάγετε το στοιχείο στην ταξινόμηση.
  4. αν το μέγεθος της ταξινόμησης είναι 1 (εισάγεται το πρώτο στοιχείο), δείξτε αριστερά και δεξιά προς το πρώτο στοιχείο ταξινόμησης.
  5. Αλλού
    1. εάν το sizeof (ταξινομημένο) είναι ομοιόμορφο, δηλαδή αριστερό και δεξιό σημείο στο ίδιο στοιχείο στη μέση.
      • εάν το τρέχον στοιχείο είναι μεγαλύτερο από το στοιχείο που δείχνει προς τα δεξιά, προχωρήστε δεξιά στο επόμενο στοιχείο.
      • αλλιώς εάν το τρέχον στοιχείο είναι μικρότερο από το στοιχείο που δείχνει προς τα δεξιά, μετακινηθείτε πίσω αριστερά στο προηγούμενο στοιχείο.
    2. αν το sizeof (ταξινομημένο) είναι μονό, δηλαδή αριστερό και δεξί σημείο σε διαδοχικά στοιχεία στο μέσο του πίνακα.
      • εάν το τρέχον στοιχείο είναι μεγαλύτερο από το στοιχείο που δείχνει προς τα δεξιά, προχωρήστε αριστερά στο επόμενο στοιχείο.
      • αλλιώς εάν το τρέχον στοιχείο είναι μικρότερο από το στοιχείο που δείχνει προς τα αριστερά, μετακινηθείτε δεξιά στο προηγούμενο στοιχείο.
      • αλλιώς εάν το τρέχον στοιχείο είναι μεγαλύτερο από αριστερά και λιγότερο από δεξιά, μετακινηθείτε αριστερά προς τα εμπρός και δεξιά προς τα πίσω.
  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

Πρόγραμμα Java για εύρεση μέσου από τη ροή δεδομένων

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. Πολυπλοκότητα χρόνου: T (n) = O (nlogn), για σχηματισμό πολλαπλών συνόλων n στοιχείων.
  2. Space Complexity: A (n) = O (n), οι τιμές ροής αποθηκεύονται σε ένα σύνολο.
Βλέπε επίσης
Αλγόριθμος KMP

αναφορές