Datenstruktur: einfügen, entfernen, enthält, zufälliges Element erhalten, alles bei O (1)

94

Dieses Problem wurde mir in einem Interview gegeben. Wie hätten Sie geantwortet?

Entwerfen Sie eine Datenstruktur, die die folgenden Operationen in O (1) -Zeit bietet:

  • einfügen
  • entfernen
  • enthält
  • zufälliges Element erhalten
Gildenbesitzer
quelle
Können wir zusätzliche Einschränkungen für die Art der Daten annehmen? als gäbe es keine Duplikate usw.
Sanjeevakumar Hiremath
Sicher, keine Duplikate, Sie können sogar integrierte Datenstrukturen in einer Sprache wie Java oder C # verwenden.
Gildenbesitzer
1
Ich stelle fest, dass es keine Spezifikation bezüglich: bestellt / ungeordnet gibt
Charles Duffy
7
Ich weiß, dass dieser Beitrag beantwortet wurde, aber für mich wäre es sinnvoller, wenn Sie o (1) wahlfreien Zugriff gewähren sollen, anstatt ein zufälliges Element zu erhalten.
Ramsinb
Haben Sie die richtige Lösung dafür gefunden?
Balaji Boggaram Ramanarayan

Antworten:

142

Stellen Sie sich eine Datenstruktur vor, die aus einer Hashtabelle H und einem Array A besteht. Die Hashtabellenschlüssel sind die Elemente in der Datenstruktur, und die Werte sind ihre Positionen im Array.

  1. Einfügen (Wert): Hänge den Wert an das Array an und lasse i seinen Index in A sein. Setze H [Wert] = i.
  2. remove (Wert): Wir werden die Zelle, die den Wert in A enthält, durch das letzte Element in A ersetzen. Sei d das letzte Element im Array A am Index m. Sei i H [Wert], der Index im Array des zu entfernenden Wertes. Setzen Sie A [i] = d, H [d] = i, verringern Sie die Größe des Arrays um eins und entfernen Sie den Wert aus H.
  3. enthält (Wert): return H. enthält (Wert)
  4. getRandomElement (): sei r = zufällig (aktuelle Größe von A). gib A [r] zurück.

Da das Array automatisch vergrößert werden muss, wird O (1) amortisiert, um ein Element hinzuzufügen, aber ich denke, das ist in Ordnung.

r0u1i
quelle
Das ist nah an dem, was ich hatte, aber ich habe die Verwendung der Elemente selbst als Schlüssel verpasst ... Ich wusste, dass ich nah dran war, aber das trifft es wirklich auf den Kopf!
Gildenbesitzer
Es ist interessant, dass ich diese Frage auf einem Google-Telefonbildschirm habe und nach einigen Schwierigkeiten an der gleichen Lösung festhielt. Ich habe eine Implementierung ein wenig vermasselt und dem zweiten Telefonbildschirm zugewiesen.
Andrey Talnikov
Wert an Array anhängen: Wie ist es O (1)?
Balaji Boggaram Ramanarayan
4
@aamadmi - nun, in Java sollte es wohl so sein. Im Pseudocode sollte enthalten sollte gut funktionieren :)
r0u1i
4
Warum ist ein Array erforderlich, warum können wir keine Hashmap verwenden?
Ankit Zalani
22

O (1) Lookup impliziert eine Hash-Datenstruktur .

Im Vergleich:

  • O (1) Einfügen / Löschen mit O (N) -Suche impliziert eine verknüpfte Liste.
  • O (1) Einfügen, O (N) Löschen und O (N) Nachschlagen implizieren eine Array-gestützte Liste
  • O (logN) Einfügen / Löschen / Nachschlagen impliziert einen Baum oder Heap.
Anon
quelle
Das ist ein Anfang, aber was ist mit der letzten Anforderung? Können Sie ein zufälliges Element (mit gleicher Wahrscheinlichkeit für jedes Element in der Datenstruktur) aus einer gehashten Datenstruktur erhalten?
Gildenbesitzer
1
@ lag1980, ich denke, Sie können:hashtable.get((int)(Math.random()*hashtable.size()));
CMR
3
Hmmm, ich kenne keine Hashtabellen, mit denen Sie ein solches Element erhalten können, und wenn es welche gibt, kann ich mir nicht vorstellen, dass dies eine konstante Zeitoperation wäre. Es würde mich interessieren, in beiden Punkten als falsch erwiesen zu werden.
Gildenbesitzer
@ lag1980 ... Sie können dies problemlos in konstanter Zeit tun, genauso wie Clojures Vektoren "konstante Zeit" sind - log32 (N), wenn die möglichen Werte von N von Ihrer Hardware so eingeschränkt werden, dass der größtmögliche log32 () -Wert ist ... so etwas wie 7, was effektiv eine konstante Zeit ist.
Charles Duffy
Mit "Array-Backed List" meinen Sie: Array?
Hengameh
5

Das mag Ihnen vielleicht nicht gefallen, weil sie wahrscheinlich nach einer cleveren Lösung suchen, aber manchmal lohnt es sich, an Ihren Waffen festzuhalten ... Eine Hash-Tabelle erfüllt bereits die Anforderungen - wahrscheinlich insgesamt besser als alles andere (wenn auch offensichtlich in amortisierter Konstante) Zeit und mit unterschiedlichen Kompromissen zu anderen Lösungen).

Die Anforderung, die schwierig ist, ist die Auswahl des "zufälligen Elements": In einer Hash-Tabelle müssten Sie nach einem solchen Element suchen oder suchen.

Bei geschlossener Hashing- / offener Adressierung besteht die Wahrscheinlichkeit, dass ein bestimmter Bucket belegt wird size() / capacity(). Entscheidend ist jedoch , dass dies durch eine Hash-Tabellen-Implementierung in der Regel in einem konstanten multiplikativen Bereich gehalten wird (z. B. kann die Tabelle um das 1,2-fache größer als ihr aktueller Inhalt gehalten werden bis ~ 10x je nach Leistung / Speicheroptimierung). Dies bedeutet, dass wir im Durchschnitt mit der Suche nach 1,2 bis 10 Eimern rechnen können - völlig unabhängig von der Gesamtgröße des Containers. amortisiertes O (1).

Ich kann mir zwei einfache Ansätze vorstellen (und viele weitere fummelige):

  • Suche linear aus einem zufälligen Eimer

    • Betrachten Sie leere / werthaltige Eimer als "--AC ----- B - D": Sie können sagen, dass die erste "zufällige" Auswahl fair ist, obwohl sie B bevorzugt, da B keine Wahrscheinlichkeit mehr hatte, bevorzugt zu werden als die anderen Elemente, aber wenn Sie wiederholte "zufällige" Auswahlen mit denselben Werten durchführen, kann es unerwünscht sein, B eindeutig bevorzugt zu haben (nichts in der Frage erfordert jedoch auch nur Wahrscheinlichkeiten).
  • Versuchen Sie es wiederholt mit zufälligen Eimern, bis Sie einen bestückten finden

    • "nur" Kapazität () / Größe () durchschnittliche besuchte Buckets (wie oben) - aber praktisch teurer, weil die Erzeugung von Zufallszahlen relativ teuer und unendlich schlecht ist, wenn das Verhalten im schlimmsten Fall unendlich unwahrscheinlich ist ...
      • Ein schnellerer Kompromiss wäre die Verwendung einer Liste vorgenerierter zufälliger Offsets aus dem ursprünglich zufällig ausgewählten Bucket, wobei% in die Bucket-Anzahl aufgenommen werden

Keine großartige Lösung, aber dennoch ein besserer Kompromiss als der Speicher- und Leistungsaufwand für die jederzeitige Aufrechterhaltung eines zweiten Indexarrays.

Tony Delroy
quelle
3

Die beste Lösung ist wahrscheinlich die Hash-Tabelle + Array, sie ist sehr schnell und deterministisch.

Aber die Antwort mit der niedrigsten Bewertung (verwenden Sie einfach eine Hash-Tabelle!) Ist auch großartig!

  • Hash-Tabelle mit erneutem Hashing oder neuer Bucket-Auswahl (dh ein Element pro Bucket, keine verknüpften Listen)
  • getRandom () versucht wiederholt, einen zufälligen Bucket auszuwählen, bis er leer ist.
  • Als Fail-Safe wählt getRandom () nach N (Anzahl der Elemente) erfolglosen Versuchen möglicherweise einen Zufallsindex i in [0, N-1] aus, geht dann die Hash-Tabelle linear durch und wählt das # i-te Element aus .

Die Leute mögen das vielleicht nicht wegen "möglicher Endlosschleifen", und ich habe gesehen, dass sehr kluge Leute diese Reaktion auch haben, aber es ist falsch! Unendlich unwahrscheinliche Ereignisse passieren einfach nicht .

Angenommen, das gute Verhalten Ihrer Pseudozufallsquelle - das für dieses spezielle Verhalten nicht schwer festzustellen ist - und die Hash-Tabellen sind immer zu mindestens 20% voll, ist dies leicht zu erkennen:

Es wird niemals passieren, dass getRandom () mehr als 1000 Mal versuchen muss. Nur nie . In der Tat beträgt die Wahrscheinlichkeit eines solchen Ereignisses 0,8 ^ 1000, was 10 ^ -97 entspricht. Wir müssten es also 10 ^ 88 Mal wiederholen, um eine Chance in einer Milliarde davon zu haben, die jemals einmal passiert. Selbst wenn dieses Programm auf allen Computern der Menschheit Vollzeit ausgeführt würde, bis die Sonne stirbt, wird dies niemals passieren.

user1147505
quelle
1
Wenn Sie sich kontinuierlich für einen zufälligen Eimer mit Wert entscheiden, führt der schlimmste Fall auf der Erde zu O (1), während Sie ein zufälliges Element auswählen
Balaji Boggaram Ramanarayan
@ user1147505 - Woher hast du diese Nummer: "0.8 ^ 1000"?
Hengameh
Wie haben Sie das erreicht: "Hash-Tabellen sind immer zu mindestens 20% voll"
Hengameh
Könnten Sie bitte die Methode schreiben, mit der Sie einen zufälligen Eimer auswählen können?
Hengameh
3

Für diese Frage werde ich zwei Datenstrukturen verwenden

  • HashMap
  • ArrayList / Array / Double LinkedList.

Schritte :-

  1. Einfügen: - Überprüfen Sie, ob X bereits in HashMap vorhanden ist. - Zeitkomplexität O (1). Wenn nicht vorhanden, dann am Ende von ArrayList hinzufügen - Zeitkomplexität O (1). Fügen Sie in HashMap auch x als Schlüssel und den letzten Index als Wert hinzu - Zeitkomplexität O (1).
  2. Entfernen: - Überprüfen Sie, ob X in HashMap vorhanden ist. - Zeitkomplexität O (1). Wenn vorhanden, suchen Sie den Index und entfernen Sie ihn aus der HashMap - Zeitkomplexität O (1). Tauschen Sie dieses Element mit dem letzten Element in ArrayList aus und entfernen Sie das letzte Element - Zeitkomplexität O (1). Aktualisieren Sie den Index des letzten Elements in HashMap - Zeitkomplexität O (1).
  3. GetRandom: - Generiert eine Zufallszahl von 0 bis zum letzten Index von ArrayList. Geben Sie das ArrayList-Element mit dem generierten Zufallsindex zurück - Zeitkomplexität O (1).
  4. Suche: - Siehe in HashMap für x als Schlüssel. - Zeitkomplexität O (1).

Code: -

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;


public class JavaApplication1 {

    public static void main(String args[]){
       Scanner sc = new Scanner(System.in);
        ArrayList<Integer> al =new ArrayList<Integer>();
        HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();  
        while(true){
            System.out.println("**menu**");
            System.out.println("1.insert");
            System.out.println("2.remove");
            System.out.println("3.search");
            System.out.println("4.rendom");
            int ch = sc.nextInt();
            switch(ch){
                case 1 : System.out.println("Enter the Element ");
                        int a = sc.nextInt();
                        if(mp.containsKey(a)){
                            System.out.println("Element is already present ");
                        }
                        else{
                            al.add(a);
                            mp.put(a, al.size()-1);

                        }
                        break;
                case 2 : System.out.println("Enter the Element Which u want to remove");
                        a = sc.nextInt();
                        if(mp.containsKey(a)){

                            int size = al.size();
                            int index = mp.get(a);

                            int last = al.get(size-1);
                            Collections.swap(al, index,  size-1);

                            al.remove(size-1);
                            mp.put(last, index);

                            System.out.println("Data Deleted");

                        }
                        else{
                            System.out.println("Data Not found");
                        }
                        break;
                case 3 : System.out.println("Enter the Element to Search");
                        a = sc.nextInt();
                        if(mp.containsKey(a)){
                            System.out.println(mp.get(a));
                        }
                        else{
                            System.out.println("Data Not Found");
                        }
                        break;
                case 4 : Random rm = new Random();
                        int index = rm.nextInt(al.size());
                        System.out.println(al.get(index));
                        break;

            }
        }
    }

}

- Zeitkomplexität O (1). - Raumkomplexität O (N).

HeadAndTail
quelle
1

Hier ist eine C # -Lösung für dieses Problem, das ich vor einiger Zeit gefunden habe, als ich dieselbe Frage gestellt habe. Es implementiert Add, Remove, Contains und Random zusammen mit anderen Standard-.NET-Schnittstellen. Nicht, dass Sie es jemals während eines Interviews so detailliert implementieren müssten, aber es ist schön, eine konkrete Lösung zu haben, die Sie sich ansehen können ...

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

/// <summary>
/// This class represents an unordered bag of items with the
/// the capability to get a random item.  All operations are O(1).
/// </summary>
/// <typeparam name="T">The type of the item.</typeparam>
public class Bag<T> : ICollection<T>, IEnumerable<T>, ICollection, IEnumerable
{
    private Dictionary<T, int> index;
    private List<T> items;
    private Random rand;
    private object syncRoot;

    /// <summary>
    /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class.
    /// </summary>
    public Bag()
        : this(0)
    {
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class.
    /// </summary>
    /// <param name="capacity">The capacity.</param>
    public Bag(int capacity)
    {
        this.index = new Dictionary<T, int>(capacity);
        this.items = new List<T>(capacity);
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="Bag&lt;T&gt;"/> class.
    /// </summary>
    /// <param name="collection">The collection.</param>
    public Bag(IEnumerable<T> collection)
    {
        this.items = new List<T>(collection);
        this.index = this.items
            .Select((value, index) => new { value, index })
            .ToDictionary(pair => pair.value, pair => pair.index);
    }

    /// <summary>
    /// Get random item from bag.
    /// </summary>
    /// <returns>Random item from bag.</returns>
    /// <exception cref="System.InvalidOperationException">
    /// The bag is empty.
    /// </exception>
    public T Random()
    {
        if (this.items.Count == 0)
        {
            throw new InvalidOperationException();
        }

        if (this.rand == null)
        {
            this.rand = new Random();
        }

        int randomIndex = this.rand.Next(0, this.items.Count);
        return this.items[randomIndex];
    }

    /// <summary>
    /// Adds the specified item.
    /// </summary>
    /// <param name="item">The item.</param>
    public void Add(T item)
    {
        this.index.Add(item, this.items.Count);
        this.items.Add(item);
    }

    /// <summary>
    /// Removes the specified item.
    /// </summary>
    /// <param name="item">The item.</param>
    /// <returns></returns>
    public bool Remove(T item)
    {
        // Replace index of value to remove with last item in values list
        int keyIndex = this.index[item];
        T lastItem = this.items[this.items.Count - 1];
        this.items[keyIndex] = lastItem;

        // Update index in dictionary for last item that was just moved
        this.index[lastItem] = keyIndex;

        // Remove old value
        this.index.Remove(item);
        this.items.RemoveAt(this.items.Count - 1);

        return true;
    }

    /// <inheritdoc />
    public bool Contains(T item)
    {
        return this.index.ContainsKey(item);
    }

    /// <inheritdoc />
    public void Clear()
    {
        this.index.Clear();
        this.items.Clear();
    }

    /// <inheritdoc />
    public int Count
    {
        get { return this.items.Count; }
    }

    /// <inheritdoc />
    public void CopyTo(T[] array, int arrayIndex)
    {
        this.items.CopyTo(array, arrayIndex);
    }

    /// <inheritdoc />
    public bool IsReadOnly
    {
        get { return false; }
    }

    /// <inheritdoc />
    public IEnumerator<T> GetEnumerator()
    {
        foreach (var value in this.items)
        {
            yield return value;
        }
    }

    /// <inheritdoc />
    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    /// <inheritdoc />
    public void CopyTo(Array array, int index)
    {
        this.CopyTo(array as T[], index);
    }

    /// <inheritdoc />
    public bool IsSynchronized
    {
        get { return false; }
    }

    /// <inheritdoc />
    public object SyncRoot
    {
        get
        {
            if (this.syncRoot == null)
            {
                Interlocked.CompareExchange<object>(
                    ref this.syncRoot,
                    new object(),
                    null);
            }

            return this.syncRoot;

        }
    }
}
Scott Lerch
quelle
Ich bin nicht sicher, ob dies funktioniert, wenn Sie doppelte Nummern haben.
AlexIIP
Duplikate werden nicht behandelt, da @guildner davon ausgeht, dass die Kommentare der Frage keine Duplikate enthalten. Wenn ein Duplikat ArgumentExceptionmit der Meldung "Ein Element mit demselben Schlüssel wurde bereits hinzugefügt" hinzugefügt wird. wird ausgelöst (aus dem zugrunde liegenden Index-Wörterbuch).
Scott Lerch
1

Wir können Hashing verwenden, um Operationen in Θ (1) Zeit zu unterstützen.

Einfügen (x) 1) Überprüfen Sie, ob x bereits vorhanden ist, indem Sie eine Hash-Map-Suche durchführen. 2) Wenn nicht vorhanden, fügen Sie es am Ende des Arrays ein. 3) Fügen Sie in der Hash-Tabelle auch x als Schlüssel und den letzten Array-Index als Index hinzu.

remove (x) 1) Überprüfen Sie, ob x vorhanden ist, indem Sie eine Hash-Map-Suche durchführen. 2) Wenn vorhanden, suchen Sie den Index und entfernen Sie ihn aus der Hash-Map. 3) Tauschen Sie das letzte Element mit diesem Element im Array aus und entfernen Sie das letzte Element. Der Austausch erfolgt, da das letzte Element in O (1) -Zeit entfernt werden kann. 4) Aktualisieren Sie den Index des letzten Elements in der Hash-Map.

getRandom () 1) Generiere eine Zufallszahl von 0 bis zum letzten Index. 2) Geben Sie das Array-Element am zufällig generierten Index zurück.

Suche (x) Suchen Sie in der Hash-Map nach x.

Shobhit Raj
quelle
1

Das ist zwar viel alt, aber da es in C ++ keine Antwort gibt, sind hier meine zwei Cent.

#include <vector>
#include <unordered_map>
#include <stdlib.h>

template <typename T> class bucket{
    int size;
    std::vector<T> v;
    std::unordered_map<T, int> m;
public:
    bucket(){
        size = 0;
        std::vector<T>* v = new std::vector<T>();
        std::unordered_map<T, int>* m = new std::unordered_map<T, int>();
    }
    void insert(const T& item){
        //prevent insertion of duplicates
        if(m.find(item) != m.end()){
            exit(-1);
        }
        v.push_back(item);
        m.emplace(item, size);
        size++;

    }
    void remove(const T& item){
        //exits if the item is not present in the list
        if(m[item] == -1){
            exit(-1);
        }else if(m.find(item) == m.end()){
            exit(-1);
        }

        int idx = m[item];
        m[v.back()] = idx;
        T itm = v[idx];
        v.insert(v.begin()+idx, v.back());
        v.erase(v.begin()+idx+1);
        v.insert(v.begin()+size, itm);
        v.erase(v.begin()+size);
        m[item] = -1;
        v.pop_back();
        size--;

    }

     T& getRandom(){
      int idx = rand()%size;
      return v[idx];

     }

     bool lookup(const T& item){
       if(m.find(item) == m.end()) return false;
       return true;

     }
    //method to check that remove has worked
    void print(){
        for(auto it = v.begin(); it != v.end(); it++){
            std::cout<<*it<<" ";
        }
    }
};

Hier ist ein Teil des Client-Codes, um die Lösung zu testen.

int main() {

    bucket<char>* b = new bucket<char>();
    b->insert('d');
    b->insert('k');
    b->insert('l');
    b->insert('h');
    b->insert('j');
    b->insert('z');
    b->insert('p');

    std::cout<<b->random()<<std::endl;
    b->print();
    std::cout<<std::endl;
    b->remove('h');
    b->print();

    return 0;
}
Antithese
quelle
0

In C # 3.0 + .NET Framework 4 ist ein Generikum Dictionary<TKey,TValue>sogar besser als eine Hashtable, da Sie die System.LinqErweiterungsmethode verwenden können, ElementAt()um in das zugrunde liegende dynamische Array zu indizieren, in dem die KeyValuePair<TKey,TValue>Elemente gespeichert sind:

using System.Linq;

Random _generator = new Random((int)DateTime.Now.Ticks);

Dictionary<string,object> _elements = new Dictionary<string,object>();

....

Public object GetRandom()
{
     return _elements.ElementAt(_generator.Next(_elements.Count)).Value;
}

Soweit ich weiß, ist eine Hashtabelle (oder deren Dictionary-Nachkommen) jedoch keine echte Lösung für dieses Problem, da Put () nur mit O (1) amortisiert werden kann, nicht mit O (1), da es sich um O (N) handelt ) an der dynamischen Größenänderungsgrenze.

Gibt es eine echte Lösung für dieses Problem? Ich kann mir nur vorstellen, dass Sie O (1) -Operationen erhalten, wenn Sie eine Dictionary / Hashtable-Anfangskapazität angeben, die um eine Größenordnung über dem liegt, was Sie voraussichtlich jemals benötigen, da Sie die Größe nie ändern müssen.

BaltoStar
quelle
Wenn Sie sehr genau wissen, was eine Hash-Tabelle ist, ist eine Größenänderung von O (N) unvermeidlich. Einige Implementierungen gehen jedoch Kompromisse ein, um die Kosten für die Größenänderung zu senken, z. B. indem die vorhandene Tabelle beibehalten wird, während eine Sekunde doppelt so groß hinzugefügt wird, oder wenn versucht wird, die Größe der vorhandenen Tabelle zu ändern (nachdem der virtuelle Adressraum und die Tabellengrößen sorgfältig an den Seitengrenzen angeordnet wurden, also nein Es ist ein Kopieren erforderlich, für das möglicherweise Speicherzuordnungen anstelle von new / malloc mem erforderlich sind. Anschließend wird in dem neuen größeren Bereich gesucht, bevor mit der Elementmigrationslogik auf den kleineren zurückgegriffen wird (in einem In-Place-Modell durch engeres Modifizieren).
Tony Delroy
0

Ich stimme Anon zu. Mit Ausnahme der letzten Anforderung, bei der ein zufälliges Element mit gleicher Fairness erforderlich ist, können alle anderen Anforderungen nur mit einem einzigen Hash-basierten DS erfüllt werden. Ich werde HashSet dafür in Java wählen. Das Modulo des Hash-Codes eines Elements gibt mir die Indexnummer des zugrunde liegenden Arrays in O (1) -Zeit. Ich kann das zum Hinzufügen, Entfernen und Enthalten von Operationen verwenden.

Ayaskant
quelle
0

Können wir das nicht mit HashSet von Java machen? Es bietet standardmäßig das Einfügen, Löschen und Suchen in O (1). Für getRandom können wir den Iterator von Set verwenden, der sowieso zufälliges Verhalten liefert. Wir können einfach das erste Element aus der Menge iterieren, ohne uns um den Rest der Elemente kümmern zu müssen

public void getRandom(){
    Iterator<integer> sitr = s.iterator();
    Integer x = sitr.next();    
    return x;
}
user1108687
quelle
0
/* Java program to design a data structure that support folloiwng operations
   in Theta(n) time
   a) Insert
   b) Delete
   c) Search
   d) getRandom */
import java.util.*;

// class to represent the required data structure
class MyDS
{
   ArrayList<Integer> arr;   // A resizable array

   // A hash where keys are array elements and vlaues are
   // indexes in arr[]
   HashMap<Integer, Integer>  hash;

   // Constructor (creates arr[] and hash)
   public MyDS()
   {
       arr = new ArrayList<Integer>();
       hash = new HashMap<Integer, Integer>();
   }

   // A Theta(1) function to add an element to MyDS
   // data structure
   void add(int x)
   {
      // If ekement is already present, then noting to do
      if (hash.get(x) != null)
          return;

      // Else put element at the end of arr[]
      int s = arr.size();
      arr.add(x);

      // And put in hash also
      hash.put(x, s);
   }

   // A Theta(1) function to remove an element from MyDS
   // data structure
   void remove(int x)
   {
       // Check if element is present
       Integer index = hash.get(x);
       if (index == null)
          return;

       // If present, then remove element from hash
       hash.remove(x);

       // Swap element with last element so that remove from
       // arr[] can be done in O(1) time
       int size = arr.size();
       Integer last = arr.get(size-1);
       Collections.swap(arr, index,  size-1);

       // Remove last element (This is O(1))
       arr.remove(size-1);

       // Update hash table for new index of last element
       hash.put(last, index);
    }

    // Returns a random element from MyDS
    int getRandom()
    {
       // Find a random index from 0 to size - 1
       Random rand = new Random();  // Choose a different seed
       int index = rand.nextInt(arr.size());

       // Return element at randomly picked index
       return arr.get(index);
    }

    // Returns index of element if element is present, otherwise null
    Integer search(int x)
    {
       return hash.get(x);
    }
}

// Driver class
class Main
{
    public static void main (String[] args)
    {
        MyDS ds = new MyDS();
        ds.add(10);
        ds.add(20);
        ds.add(30);
        ds.add(40);
        System.out.println(ds.search(30));
        ds.remove(20);
        ds.add(50);
        System.out.println(ds.search(50));
        System.out.println(ds.getRandom());`enter code here`
    }
}
Ahmed Taha
quelle
-2

Warum verwenden wir nicht epoch% arraysize, um zufällige Elemente zu finden? Das Finden der Arraygröße ist O (n), aber die amortisierte Komplexität ist O (1).

Pranay Yadav
quelle
-3

Ich denke, wir können eine doppelte Linkliste mit einer Hash-Tabelle verwenden. Der Schlüssel ist ein Element und der zugehörige Wert ist der Knoten in der doppelten Linkliste.

  1. Einfügen (H, E): Knoten in doppelte Verknüpfungsliste einfügen und Eintrag als H [E] = Knoten vornehmen; O (1)
  2. Löschen (H, E): Erhalte die Knotenadresse von H (E), gehe zum vorherigen Knoten und lösche und mache H (E) zu NULL, also O (1)
  3. enthält (H, E) und getRandom (H) sind offensichtlich O (1)
Abhinav Jaiswal
quelle
Das macht keinen Sinn.
Innosam