Βρείτε διπλότυπα σε έναν δεδομένο πίνακα όταν τα στοιχεία δεν περιορίζονται σε ένα εύρος


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις πλίθα αμαζόνα Γεγονότα MAQ UHG Optum
Παράταξη Hashing

Το πρόβλημα "Εύρεση διπλότυπων σε έναν δεδομένο πίνακα όταν τα στοιχεία δεν περιορίζονται σε ένα εύρος" δηλώνει ότι έχετε παράταξη αποτελούμενο από n ακέραιους αριθμούς. Η δήλωση προβλήματος είναι να ανακαλύψετε τα διπλά στοιχεία εάν υπάρχουν στον πίνακα. Εάν δεν υπάρχει τέτοιο στοιχείο επιστροφή -1.

Παράδειγμα

Βρείτε διπλότυπα σε έναν δεδομένο πίνακα όταν τα στοιχεία δεν περιορίζονται σε ένα εύρος

[ 2, 4, 6, 2, 7, 8, 9, 7]
2, 7

εξήγηση

Σε αυτόν τον πίνακα 2 και 7 είναι τα μόνα διπλά στοιχεία.

[134, 567, 134, 456, 1000, 567, 7]
134, 567

εξήγηση

Σε αυτόν τον πίνακα 134 και 567 είναι τα μόνα διπλά στοιχεία.

Αλγόριθμος για την εύρεση διπλών στοιχείων σε έναν πίνακα

  1. Δηλώνω χάρτη.
  2. Αποθηκεύστε το στοιχείο του πίνακα και τη συχνότητά του σε έναν χάρτη.
  3. Δηλώστε το Boolean μεταβλητή αντίγραφο για να ελέγξετε αν υπάρχει διπλό στοιχείο ή όχι.
  4. Επαναλάβετε τον χάρτη και ελέγξτε για ποιο στοιχείο έχει συχνότητα μεγαλύτερη από 1.
  5. Εάν η συχνότητα είναι μεγαλύτερη από 1, εκτυπώστε το στοιχείο και αρχικοποιήστε το αντίγραφο σε πραγματικό.
  6. Ελέγξτε εάν το αντίγραφο είναι ψευδές εάν η συνθήκη ικανοποιεί και εκτυπώστε -1.

εξήγηση

Έχουμε δώσει ένα πρόβλημα στο οποίο πρέπει να προσδιορίσουμε τα διπλά στοιχεία σε έναν πίνακα και να εκτυπώσουμε αυτά τα στοιχεία. Για αυτό, θα χρησιμοποιήσουμε ένα HashMap για την αποθήκευση των συχνοτήτων κάθε στοιχείου πίνακα. Οι συχνότητες, οι οποίες είναι μεγαλύτερες από 1, σημαίνει ότι ο αριθμός επαναλαμβάνεται στον πίνακα. Αυτό σημαίνει την αντιγραφή αυτού του αριθμού.

Έχουμε περάσει δύο ορίσματα ως πίνακα και το μήκος του. Τώρα δηλώστε μια ακόμη μεταβλητή που θα είναι Boolean μεταβλητή που αρχικοποιείται ως false. Στη συνέχεια, ελέγξτε το αργότερα, εάν δεν θα βρούμε διπλό στοιχείο τότε αντίγραφο παραμένει ψευδές αλλιώς θα είναι αλήθεια. Στη συνέχεια, χρησιμοποιώντας αυτόν τον χάρτη, ανακαλύψτε το στοιχείο που έχει συχνότητα μεγαλύτερη από 1, θα εκτυπώσουμε αυτά τα στοιχεία. Και έτσι βρίσκουμε τα διπλά στοιχεία σε έναν πίνακα.

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

arr [] = {2,4,6,3,1,2,4,7};

i = 0, arr [i] = 2; freq = {2: 1}

i=1, arr[i]=4; freq={2:1,4:1}

i=2, arr[i]=6; freq={2:1,4:1,6:1}

i=3, arr[i]=3; freq={2:1,4:1,6:1,3:1}

i=4, arr[i]=1; freq={2:1,4:1,6:1,3:1,1:1}

i = 5, arr [i] = 2; freq = {2: 2,4: 1,6: 1,3: 1,1: 1} // αύξηση της συχνότητας του '2' από 1 σε 2,

i = 6, arr [i] = 4; freq = {2: 2,4: 2,6: 1,3: 1,1: 1} // αύξηση της συχνότητας του '4' από 1 σε 2,

i=7, arr[i]=7; freq={2:2,4:2,6:1,3:1,1:1,7:1}

έχουμε συχνότητα στο χάρτη: {2: 2,4: 2,6: 1,3: 1,1: 1,7: 1}

Τώρα επαναλάβετε τον χάρτη και ανακαλύψτε ποια τιμή έχει συχνότητα μεγαλύτερη από 1. Έχουμε ήδη αρχίσει εδώ ένα αντίγραφο μεταβλητής Boolean ως ψευδές, οπότε όταν ελέγξουμε ποια συχνότητα είναι μεγαλύτερη από 1, θα ενημερώσουμε το αντίγραφο ως αληθινό. Και αν βγαίνουμε από το βρόχο με διπλότυπο ως ψευδές, αυτό σημαίνει ότι δεν υπάρχει διπλό στοιχείο σε έναν πίνακα.

Σαφώς, τα 2 και 4 έχουν συχνότητα μεγαλύτερη από ότι σημαίνει ότι είναι διπλά στοιχεία.

Και η παραγωγή μας γίνεται [2 4]. Έτσι, αυτό ήταν ένα παράδειγμα του πώς βρίσκουμε διπλά στοιχεία σε έναν πίνακα.

Κώδικας

Κωδικός C ++ για εύρεση διπλών στοιχείων σε έναν πίνακα

#include <iostream>
#include <unordered_map>

using namespace std;

void getDuplicate(int arr[], int n)
{
    unordered_map<int,int> freq;

    for(int index=0;index<n;index++)
        freq[arr[index]]++;

    bool duplicate=false;
    unordered_map<int,int> :: iterator itr;
    for(itr=freq.begin();itr!=freq.end();itr++)
    {
        if(itr->second > 1)
        {
            cout<<itr->first<<" ";
            duplicate=true;
        }
    }
    if(!duplicate)
        cout<<"-1"<<endl;
}
int main()
{
    int arr[]={2,4,6,3,1,2,4,7};
    int n=sizeof(arr)/sizeof(arr[0]);
    getDuplicate(arr,n);
    return 0;
}
4 2

Κωδικός Java για την εύρεση διπλών στοιχείων σε έναν πίνακα

import java.util.HashMap;
class findDuplicateNumber
{
    public static void getDuplicate(int arr[], int n)
    {
        HashMap<Integer, Integer> freq=new HashMap<Integer, Integer>();
        for(int i=0; i<n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i],freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i],1);
            }
        }
        boolean duplicate=false;
        for(int i:freq.keySet())
        {
            if(freq.get(i)> 1)
            {
                System.out.print(i+" ");
                duplicate=true;
            }
        }
        if(!duplicate)
            System.out.println("-1");
    }
    public static void main(String [] args)
    {
        int arr[]= {2,4,6,3,1,2,4,7};
        int len=arr.length;
        getDuplicate(arr,len);
    }
}
2 4

Ανάλυση πολυπλοκότητας

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

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα. Έτσι, το πρόβλημα "Εύρεση διπλότυπων σε μια δεδομένη συστοιχία όταν τα στοιχεία δεν περιορίζονται σε ένα εύρος" έχει γραμμική πολυπλοκότητα χρόνου.

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

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα. Η πολυπλοκότητα του χώρου είναι επίσης γραμμική, διότι στη χειρότερη περίπτωση μπορεί να έχουμε όλα τα ξεχωριστά στοιχεία.