LeetCode: Wstaw usuń getrandom o1 C #

Question

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

proszę o komentarz na temat wydajności

Zaimplementuj klasę RandomizedSet:

bool insert (int val) Wstawia element val do zestawu, jeśli go nie ma. Zwraca true, jeśli element nie był obecny, false w przeciwnym razie. bool remove (int val) Usuwa wartość elementu z zestawu, jeśli jest obecny. Zwraca true, jeśli element był obecny, false w przeciwnym razie. int getRandom () Zwraca losowy element z aktualnego zestawu elementów (gwarantuje, że co najmniej jeden element istnieje, gdy ta metoda jest wywoływana). Każdy element musi mieć takie samo prawdopodobieństwo zwrócenia. Kontynuacja: czy możesz zaimplementować funkcje klasy, gdy każda funkcja działa w średnim czasie O (1)?

Przykład 1:

Dane wejściowe ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] Dane wyjściowe [null, true, false, true, 2, true, false, 2]

Objaśnienie RandomizedSet randomizedSet = new RandomizedSet (); randomizedSet.insert (1); // Wstawia 1 do zestawu. Zwraca prawdę, ponieważ 1 został pomyślnie wstawiony. randomizedSet.remove (2); // Zwraca fałsz, ponieważ 2 nie istnieje w zestawie. randomizedSet.insert (2); // Wstawia 2 do zestawu, zwraca prawdę. Zestaw zawiera teraz [1,2]. randomizedSet.getRandom (); // getRandom () powinno losowo zwrócić 1 lub 2. randomizedSet.remove (1); // Usuwa 1 z zestawu, zwraca prawdę. Zestaw zawiera teraz [2]. randomizedSet.insert (2); // 2 było już w zestawie, więc zwróć false. randomizedSet.getRandom (); // Ponieważ 2 jest jedyną liczbą w zestawie, getRandom () zawsze zwróci 2.

Ograniczenia:

\$-2^{31} <= val <= 2^{31} - 1\$. Co najwyżej \$10^5\$będą wykonywane wywołania insert, remove i getRandom. Gdy zostanie wywołana funkcja getRandom, w strukturze danych będzie co najmniej jeden element.

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

• HashSet<int>Nie zostaną zmienione stąd uczynić go readonly.
• Zamiast wywoływania Contains()przed wywołaniem Add(), jeśli to falsewyniesie, można uprościć tylko return _set.Add(val);dlatego, że Add()metoda zwraca, falsejeśli wartość jest już w HashSet. Odniesienie
• Zamiast wywoływania Contains()przed wywołaniem Remove()można również uprościć, return _set.Remove(val);ponieważ Remove()zwróci, falsejeśli element nie znajduje się w HashSet. Odniesienie
• Wywołanie GetRandom()w krótkim czasie wielokrotnie może doprowadzić do tego samego elementu, ponieważ Seedod stworzonej Randomw .NET framework oparty jest na obecnym datownik. Lepiej jest utworzyć poziom klasy, Randomktóry będzie używany.

Podsumowując prowadzi do

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() Złożoność

HashSet<T>nie obsługuje wyszukiwania według indeksu, więc ElementAtmusi wykonywać iterację, dopóki żądany element nie zostanie osiągnięty. To wymaga O (n) kroków, a nie O (1).