Ομαδοποίηση πολλαπλών εμφανίσεων στοιχείων σειράς κατά πρώτη εμφάνιση


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Απολύτως πλίθα αμαζόνα Δελχί Fourkites
Παράταξη Χασίσι

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

Παράδειγμα

εισόδου:

[2, 3,4,3,1,3,2,4]

Παραγωγή:

[2 2 3 3 3 4 4 1]

εισόδου:

[5,4,1,5,4,1,5,6]

Παραγωγή:

[5 5 5 4 4 1 1 6]

Αλγόριθμος

  1. Δηλώνω HashMap.
  2. Διασχίστε τον πίνακα και τοποθετήστε όλα τα στοιχεία και τη συχνότητά του στο HashMap.
  3. Διασχίζοντας τον πίνακα και λάβετε τη συχνότητα κάθε στοιχείου.
    1. Εκτυπώστε αυτό το κλειδί έως τους χρόνους συχνότητας.
    2. Αφαιρέστε το arr [i] (κλειδί).

Επεξήγηση για την Ομάδα πολλαπλών εμφανίσεων στοιχείων συστοιχίας

Θα χρησιμοποιήσουμε το Hashing για αυτό. Το κατακερματισμό παρέχει μια δυνατότητα αποθήκευσης των στοιχείων ως ζεύγος τιμών-κλειδιών. Σε αυτήν την ερώτηση, πρόκειται να χρησιμοποιήσουμε ένα κλειδί ως στοιχείο πίνακα και μια τιμή ως συχνότητα κάθε στοιχείου. Εισάγουμε απλώς το στοιχείο εάν δεν υπάρχει στον πίνακα κατακερματισμού. αλλιώς αυξήστε το πλήθος (τιμή-κλειδί) του στοιχείου.

Πρώτον, θα δηλώσουμε ένα HashMap να λέει "myMap". Στη συνέχεια διασχίζουμε ολόκληρη τη σειρά και μετράμε και αποθηκεύουμε το συχνότητα κάθε στοιχείου.

Ας εξετάσουμε ένα παράδειγμα και να το κατανοήσουμε.

Παράδειγμα

arr = [5, 4, 1, 5, 4, 1, 5, 6]

i = 0, arr [i] = 5

myMap = {5: 1}

i = 1, arr [i] = 4

myMap = {4: 1,5: 1}

i = 2, arr [i] = 1

myMap = {1: 1,4: 1,5: 1}

i = 3, arr [i] = 5

myMap = {1: 1,4: 1,5: 2}

i = 4, arr [i] = 4

myMap = {1: 1,4: 2,5: 2}

i = 5, arr [i] = 1

myMap = {1: 2,4: 2,5: 2}

i = 6, arr [i] = 5

myMap = {1: 2,4: 2,5: 3}

i = 6, arr [i] = 6

myMap={1:2,4:2,5:3,6:1}

Τώρα θα έχουμε ένα myMap και τιμές σε αυτό.

Θα λάβουμε τη συχνότητα αφού διασχίσουμε ξανά έναν πίνακα με το διατεταγμένο στοιχείο σε έναν πίνακα. Λαμβάνοντας κάθε στοιχείο συστοιχίας με τη συχνότητά του και κάντε έναν βρόχο μέχρι τον συγκεκριμένο χρόνο συχνότητας και μετά την εκτύπωση όλων των στοιχείων συστοιχίας έως ότου οι χρόνοι συχνότητας αφαιρέσουν αυτό το κλειδί συστοιχίας έτσι ώστε να μην εκτυπώνονται ξανά στην περαιτέρω διασταύρωση.

Arr [i] = 5 συχνότητα = 3

5 θα εκτυπωθούν, 3 φορές, τότε θα αφαιρέσουμε αυτό το κλειδί στο myMap, οπότε όποτε διαβάζουμε 5 σε έναν πίνακα δεν θα υπάρχει στο hashmap και δεν εκτυπώνεται.

Arr [i] = 4 συχνότητα = 2

4 θα εκτυπωθούν, 2 φορές, το κλειδί θα αφαιρεθεί στο myMap, οπότε όποτε διαβάζουμε 4 σε έναν πίνακα δεν θα υπάρχει στο HashMap και δεν εκτυπώνεται.

Arr [i] = 1 συχνότητα = 2

1 θα εκτυπωθεί, 2 φορές, τότε θα αφαιρέσουμε αυτό το κλειδί στο myMap, οπότε όποτε διαβάζουμε 5 σε έναν πίνακα και δεν θα υπάρχει στο HashMap και δεν εκτυπώνεται.

Τώρα 5 έρχεται σε σειρά, αλλά δεν θα υπάρχει στο HashMap και το ίδιο συμβαίνει και δεν κάνει τίποτα μέχρι να βρεθεί το στοιχείο που υπάρχει στο HashMap.

Arr [i] = 6 συχνότητα = 1

6 θα εκτυπωθεί, 1 φορά, το κλειδί θα αφαιρεθεί στο myMap, οπότε όποτε διαβάζουμε 4 στον πίνακα δεν θα υπάρχει στο hashmap και δεν εκτυπώνεται.

Θα έχουμε την έξοδο τώρα ως 5 5 5 4 4 1 1 6.

Εκτέλεση

Πρόγραμμα C ++ για Ομαδικές πολλαπλές εμφανίσεις στοιχείων παραγγελίας κατά πρώτη εμφάνιση

#include<iostream>
#include<unordered_map>

using namespace std;
void arrangeInOrder(int arr[], int n)
{
    unordered_map<int, int> myMap;

    for (int i=0; i<n; i++)
    {
        myMap[arr[i]]++;
    }
    for (int i=0; i<n; i++)
    {
        int count = myMap[arr[i]];
        for (int j=0; j<count; j++)
            cout<<arr[i]<< " ";

        myMap.erase(arr[i]);
    }
}
int main()
{
    int arr[] = {10, 5, 3, 10, 10, 4, 1, 3};
    int n=sizeof(arr)/sizeof(arr[0]);
    arrangeInOrder(arr,n);
    return 0;
}
10 10 10 5 3 3 4 1

Πρόγραμμα Java

import java.util.HashMap;

class multipleOccurences
{
    public static void arrangeInOrder(int arr[])
    {
        HashMap<Integer, Integer> myMap= new HashMap<Integer, Integer>();

        for (int i=0; i<arr.length; i++)
        {
            Integer current = myMap.get(arr[i]);
            if (current == null)
                current = 0;

            myMap.put(arr[i], current + 1);
        }
        for (int i=0; i<arr.length; i++)
        {
            Integer count = myMap.get(arr[i]);
            if (count != null)
            {
                for (int j=0; j<count; j++)
                {
                    System.out.print(arr[i] + " ");
                }
                myMap.remove(arr[i]);
            }
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 5, 3, 10, 10, 4, 1, 3};
        arrangeInOrder(arr);
    }
}
10 10 10 5 3 3 4 1

Ανάλυση πολυπλοκότητας για πολλαπλές εμφανίσεις ομάδων στοιχείων συστοιχίας

Χρόνος πολυπλοκότητας

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

Διαστημική πολυπλοκότητα

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

Αναφορά