LeetCode: Insertar eliminar getrandom o1 C #

Question

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

por favor comente sobre el desempeño

Implemente la clase RandomizedSet:

bool insert (int val) Inserta un elemento val en el conjunto si no está presente. Devuelve verdadero si el artículo no estaba presente, falso en caso contrario. bool remove (int val) Elimina un elemento val del conjunto si está presente. Devuelve verdadero si el elemento estaba presente, falso en caso contrario. int getRandom () Devuelve un elemento aleatorio del conjunto actual de elementos (se garantiza que existe al menos un elemento cuando se llama a este método). Cada elemento debe tener la misma probabilidad de ser devuelto. Seguimiento: ¿Podrías implementar las funciones de la clase con cada función trabaja en un tiempo promedio de O (1)?

Ejemplo 1:

Introduzca ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] Salida [nulo, verdadero, falso, verdadero, 2, verdadero, falso, 2]

Explicación RandomizedSet randomizedSet = new RandomizedSet (); randomizedSet.insert (1); // Inserta 1 al conjunto. Devuelve verdadero ya que 1 se insertó correctamente. randomizedSet.remove (2); // Devuelve falso ya que 2 no existe en el conjunto. randomizedSet.insert (2); // Inserta 2 al conjunto, devuelve verdadero. El conjunto ahora contiene [1,2]. randomizedSet.getRandom (); // getRandom () debe devolver 1 o 2 al azar. randomizedSet.remove (1); // Elimina 1 del conjunto, devuelve verdadero. El conjunto ahora contiene [2]. randomizedSet.insert (2); // 2 ya estaba en el conjunto, así que devuelve falso. randomizedSet.getRandom (); // Dado que 2 es el único número del conjunto, getRandom () siempre devolverá 2.

Limitaciones:

\$-2^{31} <= val <= 2^{31} - 1\$. Como máximo \$10^5\$se realizarán llamadas para insertar, eliminar y getRandom. Habrá al menos un elemento en la estructura de datos cuando se llame a 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

• El HashSet<int>no se cambiará por lo tanto, hacen que sea readonly.
• En lugar de llamar Contains()antes de la llamada a Add(), si esto se evalúa como false, se puede simplificar a solo return _set.Add(val);porque el Add()método regresa falsesi el valor ya está en HashSet. Referencia
• En lugar de llamar Contains()antes de llamar, también Remove()se puede simplificar a solo return _set.Remove(val);porque Remove()regresará falsesi el elemento no está en HashSet. Referencia
• Llamar GetRandom()repetidamente en un orden corto puede resultar en el mismo elemento porque el Seedde un Randommarco creado en .NET se basa en la marca de tiempo actual. Es mejor crear un nivel de clase Randompara usar.

Resumir conduce 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() Complejidad

HashSet<T>no admite la búsqueda por índice, por lo que ElementAtdebe iterar hasta que se alcance el elemento solicitado. Eso requiere O (n) pasos, no O (1).