LeetCode: getrandom o1 C # silme ekle

Question

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

lütfen performans hakkında yorum yapın

RandomizedSet sınıfını uygulayın:

bool insert (int val) Eğer yoksa sete bir öğe val ekler. Öğe yoksa doğru, aksi takdirde yanlış döndürür. bool remove (int val) Varsa, kümeden bir val öğesini kaldırır. Öğe mevcutsa true, aksi takdirde false döndürür. int getRandom () Geçerli öğe kümesinden rastgele bir öğe döndürür (bu yöntem çağrıldığında en az bir öğenin var olduğu garanti edilir). Her eleman aynı iade olasılığına sahip olmalıdır. Takip: Sınıfın fonksiyonlarını her bir fonksiyon ortalama O (1) süresinde çalışabilir mi?

Örnek 1:

Giriş ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] Çıktı [null, true, false, true, 2, true, false, 2]

Açıklama RandomizedSet randomizedSet = new RandomizedSet (); randomizedSet.insert (1); // Sete 1 ekler. 1 başarıyla eklendiğinde doğru döndürür. randomizedSet.remove (2); // Kümede 2 olmadığı için yanlış döndürür. randomizedSet.insert (2); // Sete 2 ekler, true döndürür. Şimdi set [1,2] içerir. randomizedSet.getRandom (); // getRandom () rastgele 1 veya 2 döndürmelidir. randomizedSet.remove (1); // Setten 1'i çıkarır, true döndürür. Set şimdi [2] içerir. randomizedSet.insert (2); // 2 zaten kümedeydi, bu yüzden yanlış döndür. randomizedSet.getRandom (); // Kümedeki tek sayı 2 olduğu için getRandom () her zaman 2 döndürür.

Kısıtlamalar:

\$-2^{31} <= val <= 2^{31} - 1\$. En çok \$10^5\$eklemek, kaldırmak ve getRandom için çağrılar yapılacaktır. GetRandom çağrıldığında veri yapısında en az bir öğe olacaktır.

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

• Bu HashSet<int>yüzden değiştirilmeyecek readonly.
• Bunun yerine çağıran Contains()önce çağrısına için Add(), bu değerlendirir eğer false, basitleştirilmiş olabilir sadece return _set.Add(val);çünkü Add()yöntem getiri falsedeğeri allready ise HashSet. Referans
• Bunun yerine çağıran Contains()önce çağrılmadan Remove()hemen yanı basitleştirilmiş olabilir return _set.Remove(val);çünkü Remove()dönecektir falseöğesi değilse HashSet. Referans
• .NET çerçevesinde oluşturulan bir GetRandom()öğenin geçerli zaman damgasını temel Seedalması nedeniyle, tekrar tekrar kısa sırayla çağrı yapmak aynı öğeyle sonuçlanabilir Random. RandomKullanılacak bir sınıf seviyesi oluşturmak daha iyidir .

Özetlemek yol açar

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() Karmaşıklık

HashSet<T>dizine göre aramayı desteklemez, bu nedenle ElementAtistenen öğeye ulaşılıncaya kadar yinelenmesi gerekir. Bu, O (1) değil O (n) adımlarını gerektirir.