LeetCode: Einfügen löschen getrandom o1 C # einfügen

Question

https://leetcode.com/problems/insert-delete-getrandom-o1/

Bitte kommentieren Sie die Leistung

Implementieren Sie die RandomizedSet-Klasse:

bool insert (int val) Fügt ein Element val in das Set ein, wenn es nicht vorhanden ist. Gibt true zurück, wenn das Element nicht vorhanden war, andernfalls false. bool remove (int val) Entfernt ein Element val aus dem Set, falls vorhanden. Gibt true zurück, wenn das Element vorhanden war, andernfalls false. int getRandom () Gibt ein zufälliges Element aus der aktuellen Elementmenge zurück (es ist garantiert, dass mindestens ein Element vorhanden ist, wenn diese Methode aufgerufen wird). Jedes Element muss die gleiche Wahrscheinlichkeit haben, zurückgegeben zu werden. Follow-up: Könnten Sie die Funktionen der Klasse implementieren, wobei jede Funktion in durchschnittlicher O (1) -Zeit funktioniert?

Beispiel 1:

Geben Sie ["RandomizedSet", "Einfügen", "Entfernen", "Einfügen", "GetRandom", "Entfernen", "Einfügen", "GetRandom" ein] [[], [1], [2], [2], [], [1], [2], []] Ausgabe [null, wahr, falsch, wahr, 2, wahr, falsch, 2]

Erläuterung RandomizedSet randomSet = new RandomizedSet (); randomisiertSet.insert (1); // Fügt 1 in die Menge ein. Gibt true zurück, da 1 erfolgreich eingefügt wurde. randomSet.remove (2); // Gibt false zurück, da 2 nicht in der Menge vorhanden ist. randomisiertSet.insert (2); // Fügt 2 in die Menge ein und gibt true zurück. Set enthält jetzt [1,2]. randomSet.getRandom (); // getRandom () sollte zufällig entweder 1 oder 2 zurückgeben. randomSet.remove (1); // Entfernt 1 aus der Menge und gibt true zurück. Set enthält jetzt [2]. randomisiertSet.insert (2); // 2 war bereits im Set, also return false. randomSet.getRandom (); // Da 2 die einzige Zahl in der Menge ist, gibt getRandom () immer 2 zurück.

Einschränkungen:

\.$-2^{31} <= val <= 2^{31} - 1\$. Höchstens \$10^5\$Es werden Aufrufe zum Einfügen, Entfernen und GetRandom ausgeführt. Wenn getRandom aufgerufen wird, befindet sich mindestens ein Element in der Datenstruktur.

public class RandomizedSet {
    
     private HashSet<int> _set;
        /** Initialize your data structure here. */
        public RandomizedSet()
        {
            _set = new HashSet<int>();
        }

        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public bool Insert(int val)
        {
            if (_set.Contains(val))
            {
                return false;
            }
            _set.Add(val);
            return true;
        }

        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public bool Remove(int val)
        {
            if (_set.Contains(val))
            {
                _set.Remove(val);
                return true;
            }
            return false;
        }

        /** Get a random element from the set. */
        public int GetRandom()
        {
            Random rand = new Random();
            int key = rand.Next(_set.Count);
            return _set.ElementAt(key);
        }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * bool param_1 = obj.Insert(val);
 * bool param_2 = obj.Remove(val);
 * int param_3 = obj.GetRandom();
 */

Answer 1

• Das HashSet<int>wird nicht geändert, also mach es readonly.
• Anstatt Contains()vor dem Aufruf von aufzurufen, kann Add(), wenn dies ausgewertet wird false, vereinfacht werden, nur return _set.Add(val);weil die Add()Methode zurückgibt, falsewenn der Wert bereits in der ist HashSet. Referenz
• Anstatt vor dem Anruf Contains()anzurufen, Remove()kann auch vereinfacht werden, nur return _set.Remove(val);weil zurückgegeben Remove()wird, falsewenn das Element nicht in der ist HashSet. Referenz
• Das GetRandom()wiederholte Aufrufen in kurzer Reihenfolge kann zu demselben Element führen, da das in .NET Framework Seederstellte Element Randomauf dem aktuellen Zeitstempel basiert. Es ist besser, eine Klassenebene zu erstellen Random, die verwendet werden soll.

Zusammenfassen führt zu

public class RandomizedSet {
    
    private readonly HashSet<int> _set;
    /** Initialize your data structure here. */
    public RandomizedSet()
    {
        _set = new HashSet<int>();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public bool Insert(int val)
    {
        return _set.Add(val);
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public bool Remove(int val)
    {
        return _set.Remove(val);
    }

    private readonly Random rand = new Random();
    /** Get a random element from the set. */
    public int GetRandom()
    {
        int key = rand.Next(_set.Count);
        return _set.ElementAt(key);
    }
}

Answer 2

GetRandom() Komplexität

HashSet<T>unterstützt die Suche nach Index nicht und ElementAtmuss daher wiederholt werden, bis das angeforderte Element erreicht ist. Dies erfordert O (n) Schritte, nicht O (1).