LeetCode: Sisipkan hapus getrandom o1 C #

Question

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

tolong komentari performanya

Implementasikan kelas RandomizedSet:

bool insert (int val) Menyisipkan item val ke dalam set jika tidak ada. Mengembalikan nilai benar jika item tidak ada, salah jika tidak. bool remove (int val) Menghapus item val dari set jika ada. Mengembalikan nilai benar jika item ada, salah jika tidak. int getRandom () Mengembalikan elemen acak dari kumpulan elemen saat ini (dijamin bahwa setidaknya satu elemen ada saat metode ini dipanggil). Setiap elemen harus memiliki kemungkinan yang sama untuk dikembalikan. Tindak lanjut: Bisakah Anda mengimplementasikan fungsi kelas dengan setiap fungsi bekerja dalam waktu rata-rata O (1)?

Contoh 1:

Masukkan ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] Keluaran [nol, benar, salah, benar, 2, benar, salah, 2]

Penjelasan RandomizedSet randomizedSet = new RandomizedSet (); randomizedSet.insert (1); // Menyisipkan 1 ke set. Mengembalikan nilai benar saat 1 berhasil dimasukkan. randomizedSet.remove (2); // Mengembalikan nilai salah karena 2 tidak ada di set. randomizedSet.insert (2); // Menyisipkan 2 ke set, mengembalikan nilai true. Set sekarang berisi [1,2]. randomizedSet.getRandom (); // getRandom () harus mengembalikan 1 atau 2 secara acak. randomizedSet.remove (1); // Menghapus 1 dari set, mengembalikan nilai true. Set sekarang berisi [2]. randomizedSet.insert (2); // 2 sudah ada di set, jadi kembalikan false. randomizedSet.getRandom (); // Karena 2 adalah satu-satunya angka di set, getRandom () akan selalu mengembalikan 2.

Batasan:

\$-2^{31} <= val <= 2^{31} - 1\$. Paling banyak \$10^5\$panggilan akan dilakukan untuk memasukkan, menghapus, dan getRandom. Setidaknya akan ada satu elemen dalam struktur data saat getRandom dipanggil.

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

• Itu HashSet<int>tidak akan diubah, maka buatlah readonly.
• Alih-alih memanggil Contains()sebelum panggilan ke Add(), jika ini bernilai false, bisa disederhanakan menjadi hanya return _set.Add(val);karena Add()metode kembali falsejika nilai sudah ada di HashSet. Referensi
• Alih-alih menelepon Contains()sebelum menelepon Remove()dapat disederhanakan juga menjadi hanya return _set.Remove(val);karena Remove()akan kembali falsejika item tersebut tidak ada di HashSet. Referensi
• Memanggil GetRandom()berulang kali dalam waktu singkat dapat menghasilkan elemen yang sama karena yang Seeddibuat Randomdalam kerangka .NET didasarkan pada stempel waktu saat ini. Lebih baik membuat tingkat kelas Randomuntuk digunakan.

Menjumlahkan mengarah ke

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

HashSet<T>tidak mendukung pencarian menurut indeks sehingga ElementAtperlu mengulang hingga elemen yang diminta tercapai. Itu membutuhkan langkah O (n) bukan O (1).