LeetCode: Chèn xóa getrandom o1 C #

Question

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

vui lòng nhận xét về hiệu suất

Triển khai lớp RandomizedSet:

bool insert (int val) Chèn val item vào tập hợp nếu không có. Trả về true nếu không có mặt hàng, nếu không thì trả về false. bool remove (int val) Loại bỏ val item khỏi tập hợp nếu có. Trả về true nếu có mặt hàng, nếu không thì trả về false. int getRandom () Trả về một phần tử ngẫu nhiên từ tập hợp các phần tử hiện tại (nó được đảm bảo rằng ít nhất một phần tử tồn tại khi phương thức này được gọi). Mỗi phần tử phải có cùng một xác suất được trả về. Tiếp theo: Bạn có thể triển khai các chức năng của lớp với mỗi chức năng hoạt động trong thời gian trung bình O (1) không?

Ví dụ 1:

Đầu vào ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] Đầu ra [null, true, false, true, 2, true, false, 2]

Giải thích RandomizedSet randomizedSet = new RandomizedSet (); randomizedSet.insert (1); // Chèn 1 vào tập hợp. Trả về true khi 1 được chèn thành công. randomizedSet.remove (2); // Trả về false vì 2 không tồn tại trong tập hợp. randomizedSet.insert (2); // Chèn 2 vào tập hợp, trả về true. Đặt bây giờ chứa [1,2]. randomizedSet.getRandom (); // getRandom () sẽ trả về 1 hoặc 2 ngẫu nhiên. randomizedSet.remove (1); // Loại bỏ 1 khỏi tập hợp, trả về true. Đặt bây giờ chứa [2]. randomizedSet.insert (2); // 2 đã có trong tập hợp, vì vậy trả về false. randomizedSet.getRandom (); // Vì 2 là số duy nhất trong tập hợp, getRandom () sẽ luôn trả về 2.

Ràng buộc:

\$-2^{31} <= val <= 2^{31} - 1\$. Nhiều nhất \$10^5\$sẽ được thực hiện để chèn, loại bỏ và getRandom. Sẽ có ít nhất một phần tử trong cấu trúc dữ liệu khi getRandom được gọi.

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

• Do đó HashSet<int>sẽ không thay đổi được readonly.
• Thay vì gọi Contains()trước lệnh gọi tới Add(), nếu điều này đánh giá là false, có thể được đơn giản hóa thành chỉ return _set.Add(val);vì Add()phương thức trả về falsenếu giá trị đã nằm trong HashSet. Tài liệu tham khảo
• Thay vì gọi Contains()trước khi gọi Remove()cũng có thể được đơn giản hóa chỉ return _set.Remove(val);vì Remove()sẽ trả về falsenếu mục không có trong HashSet. Tài liệu tham khảo
• Việc gọi GetRandom()lặp lại theo thứ tự ngắn có thể dẫn đến cùng một phần tử vì phần tử Seedcủa Randomkhuôn khổ .NET được tạo dựa trên dấu thời gian hiện tại. Tốt hơn là tạo một cấp độ lớp Randomđể sử dụng.

Tổng hợp dẫn đến

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() Phức tạp

HashSet<T>không hỗ trợ tra cứu theo chỉ mục vì vậy ElementAtcần lặp lại cho đến khi đạt được phần tử được yêu cầu. Điều đó yêu cầu O (n) bước chứ không phải O (1).