LeetCode: Insérer supprimer getrandom o1 C #

Question

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

veuillez commenter les performances

Implémentez la classe RandomizedSet:

bool insert (int val) Insère un élément val dans l'ensemble s'il n'est pas présent. Renvoie vrai si l'élément n'était pas présent, faux dans le cas contraire. bool remove (int val) Supprime une valeur d'élément de l'ensemble si elle est présente. Renvoie true si l'élément était présent, false dans le cas contraire. int getRandom () Renvoie un élément aléatoire de l'ensemble actuel d'éléments (il est garanti qu'au moins un élément existe lorsque cette méthode est appelée). Chaque élément doit avoir la même probabilité d'être renvoyé. Suivi: Pourriez-vous implémenter les fonctions de la classe avec chaque fonction fonctionne en temps moyen O (1)?

Exemple 1:

Input ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] Sortie [null, vrai, faux, vrai, 2, vrai, faux, 2]

Explication RandomizedSet randomizedSet = new RandomizedSet (); randomizedSet.insert (1); // Insère 1 dans l'ensemble. Renvoie true car 1 a été inséré avec succès. randomizedSet.remove (2); // Renvoie false car 2 n'existe pas dans l'ensemble. randomizedSet.insert (2); // Insère 2 dans l'ensemble, retourne true. L'ensemble contient maintenant [1,2]. randomizedSet.getRandom (); // getRandom () doit renvoyer 1 ou 2 au hasard. randomizedSet.remove (1); // Supprime 1 de l'ensemble, renvoie vrai. L'ensemble contient maintenant [2]. randomizedSet.insert (2); // 2 était déjà dans l'ensemble, donc retournez false. randomizedSet.getRandom (); // Puisque 2 est le seul nombre de l'ensemble, getRandom () retournera toujours 2.

Contraintes:

\$-2^{31} <= val <= 2^{31} - 1\$. Au plus \$10^5\$des appels seront effectués pour insérer, supprimer et getRandom. Il y aura au moins un élément dans la structure de données lorsque getRandom sera appelé.

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

• Le HashSet<int>ne sera pas changé donc faites-le readonly.
• Au lieu d'appeler Contains()avant l'appel à Add(), si cela correspond à false, peut être simplifié simplement return _set.Add(val);parce que la Add()méthode retourne falsesi la valeur est déjà dans le HashSet. Référence
• Au lieu d'appeler Contains()avant d'appeler, cela Remove()peut également être simplifié, return _set.Remove(val);car Remove()il reviendra falsesi l'élément n'est pas dans le fichier HashSet. Référence
• L'appel GetRandom()répété dans un ordre court peut entraîner le même élément car le Seedd'un Randomframework créé dans .NET est basé sur l'horodatage actuel. Il est préférable de créer un niveau Randomde classe à utiliser.

Résumer conduit à

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() Complexité

HashSet<T>ne prend pas en charge la recherche par index et ElementAtdoit donc itérer jusqu'à ce que l'élément demandé soit atteint. Cela nécessite des étapes O (n) et non O (1).