LeetCode: Inserisci cancella getrandom o1 C #

Question

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

si prega di commentare le prestazioni

Implementa la classe RandomizedSet:

bool insert (int val) Inserisce un elemento val nel set se non presente. Restituisce vero se l'elemento non era presente, falso in caso contrario. bool remove (int val) Rimuove un elemento val dall'insieme, se presente. Restituisce vero se l'elemento era presente, falso in caso contrario. int getRandom () Restituisce un elemento casuale dall'insieme di elementi corrente (è garantito che esista almeno un elemento quando viene chiamato questo metodo). Ogni elemento deve avere la stessa probabilità di essere restituito. Follow up: potresti implementare le funzioni della classe con ogni funzione che funziona in un tempo medio O (1)?

Esempio 1:

Input ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] Output [null, true, false, true, 2, true, false, 2]

Spiegazione RandomizedSet randomizedSet = new RandomizedSet (); randomizedSet.insert (1); // Inserisce 1 nel set. Restituisce vero poiché 1 è stato inserito correttamente. randomizedSet.remove (2); // Restituisce false poiché 2 non esiste nel set. randomizedSet.insert (2); // Inserisce 2 nel set, restituisce true. Il set ora contiene [1,2]. randomizedSet.getRandom (); // getRandom () dovrebbe restituire 1 o 2 in modo casuale. randomizedSet.remove (1); // Rimuove 1 dall'insieme, restituisce true. Il set ora contiene [2]. randomizedSet.insert (2); // 2 era già nel set, quindi restituisci false. randomizedSet.getRandom (); // Dato che 2 è l'unico numero nel set, getRandom () restituirà sempre 2.

Vincoli:

\$-2^{31} <= val <= 2^{31} - 1\$. Al massimo \$10^5\$verranno effettuate chiamate per inserire, rimuovere e getRandom. Ci sarà almeno un elemento nella struttura dati quando viene chiamato getRandom.

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

• Il HashSet<int>non sarà cambiato quindi fallo readonly.
• Invece di chiamare Contains()prima della chiamata a Add(), se restituisce false, può essere semplificato a solo return _set.Add(val);perché il Add()metodo restituisce falsese il valore è già nel file HashSet. Riferimento
• Invece di chiamare Contains()prima di chiamare Remove()può essere semplificato anche solo return _set.Remove(val);perché Remove()tornerà falsese l'elemento non è nel file HashSet. Riferimento
• La chiamata GetRandom()in ordine ripetutamente breve può restituire lo stesso elemento perché il Seeddi un creato Randomin .NET framework si basa sul timestamp corrente. È meglio creare un livello Randomdi classe da utilizzare.

Riassumendo porta a

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() Complessità

HashSet<T>non supporta la ricerca per indice, quindi è ElementAtnecessario iterare finché non viene raggiunto l'elemento richiesto. Ciò richiede O (n) passaggi non O (1).