LeetCode: Inserir excluir getrandom o1 C #

Question

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

por favor, comente sobre o desempenho

Implemente a classe RandomizedSet:

bool insert (int val) Insere um item val no conjunto se não estiver presente. Retorna verdadeiro se o item não estava presente, falso caso contrário. bool remove (int val) Remove um item val do conjunto, se presente. Retorna verdadeiro se o item estava presente, falso caso contrário. int getRandom () Retorna um elemento aleatório do conjunto atual de elementos (é garantido que pelo menos um elemento existe quando este método é chamado). Cada elemento deve ter a mesma probabilidade de ser retornado. Acompanhamento: Você poderia implementar as funções da classe com cada função funcionando em média O (1) tempo?

Exemplo 1:

Insira ["RandomizedSet", "inserir", "remover", "inserir", "getRandom", "remover", "inserir", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] Saída [nulo, verdadeiro, falso, verdadeiro, 2, verdadeiro, falso, 2]

Explicação RandomizedSet randomizedSet = new RandomizedSet (); randomizedSet.insert (1); // Insere 1 no conjunto. Retorna verdadeiro porque 1 foi inserido com sucesso. randomizedSet.remove (2); // Retorna falso, pois 2 não existe no conjunto. randomizedSet.insert (2); // Insere 2 no conjunto e retorna verdadeiro. Definir agora contém [1,2]. randomizedSet.getRandom (); // getRandom () deve retornar 1 ou 2 aleatoriamente. randomizedSet.remove (1); // Remove 1 do conjunto e retorna verdadeiro. Definir agora contém [2]. randomizedSet.insert (2); // 2 já estava no conjunto, então retorna falso. randomizedSet.getRandom (); // Como 2 é o único número no conjunto, getRandom () sempre retornará 2.

Restrições:

\$-2^{31} <= val <= 2^{31} - 1\$. No máximo \$10^5\$chamadas serão feitas para inserir, remover e getRandom. Haverá pelo menos um elemento na estrutura de dados quando getRandom for chamado.

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

• O HashSet<int>não será alterado, portanto, faça-o readonly.
• Em vez de chamar Contains()antes da chamada para Add(), se for avaliado como false, pode ser simplificado para apenas return _set.Add(val);porque o Add()método retorna falsese o valor já estiver no HashSet. Referência
• Em vez de ligar Contains()antes de ligar, também Remove()pode ser simplificado para apenas return _set.Remove(val);porque Remove()retornará falsese o item não estiver no HashSet. Referência
• Chamar GetRandom()repetidamente em ordem curta pode resultar no mesmo elemento porque o Seedde um Randomframework .NET criado é baseado no carimbo de data / hora atual. É melhor criar um nível de classe Randoma ser usado.

Resumindo leads para

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() Complexidade

HashSet<T>não oferece suporte a pesquisa por índice, portanto, ElementAtprecisa iterar até que o elemento solicitado seja alcançado. Isso requer etapas O (n), não O (1).