LeetCode : 삭제 getrandom o1 C # 삽입

Question

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

성능에 대해 언급 해주세요

RandomizedSet 클래스를 구현하십시오.

bool insert (int val) 존재하지 않는 경우 항목 val을 세트에 삽입합니다. 항목이 없으면 true를 반환하고 그렇지 않으면 false를 반환합니다. bool remove (int val) 세트에서 항목 val이있는 경우 제거합니다. 항목이 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다. int getRandom () 현재 요소 집합에서 임의의 요소를 반환합니다 (이 메서드가 호출 될 때 최소한 하나의 요소가 존재 함을 보장합니다). 각 요소는 반환 될 확률이 동일해야합니다. 후속 조치 : 각 함수가 평균 O (1) 시간에 작동하는 클래스의 함수를 구현할 수 있습니까?

예 1 :

입력 [ "RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] 출력 [null, true, false, true, 2, true, false, 2]

설명 RandomizedSet randomizedSet = new RandomizedSet (); randomizedSet.insert (1); // 세트에 1을 삽입합니다. 1이 성공적으로 삽입되었으므로 true를 반환합니다. randomizedSet.remove (2); // 세트에 2가 존재하지 않으므로 false를 반환합니다. randomizedSet.insert (2); // 세트에 2를 삽입하고 true를 반환합니다. 이제 세트에 [1,2]가 포함됩니다. randomizedSet.getRandom (); // getRandom ()은 1 또는 2를 무작위로 반환해야합니다. randomizedSet.remove (1); // 세트에서 1을 제거하고 true를 반환합니다. 세트는 이제 [2]를 포함합니다. randomizedSet.insert (2); // 2가 이미 세트에 있으므로 false를 반환합니다. randomizedSet.getRandom (); // 2가 세트의 유일한 숫자이므로 getRandom ()은 항상 2를 반환합니다.

제약 :

\$-2^{31} <= val <= 2^{31} - 1\$. 최대 \$10^5\$삽입, 제거 및 getRandom을 호출합니다. getRandom이 호출되면 데이터 구조에 하나 이상의 요소가 있습니다.

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>따라서 변경을 할 수 없습니다 readonly.
• 대신 호출하는 Contains()전에 호출하는 Add()이 평가됩니다에 경우 false에 간단하게 할 수 단지 return _set.Add(val);때문에 Add()메소드가 리턴 false값이에서 allready 인 경우 HashSet. 참고
• 대신에 호출 Contains()하기 전에 호출에 Remove()단지로도 간단하게 할 수 return _set.Remove(val);있기 때문에 Remove()반환 false항목이 아닌 경우 HashSet. 참고
• .NET 프레임 워크에서 생성 된의가 현재 타임 스탬프를 기반으로 GetRandom()하기 때문에 반복적으로 짧은 순서로 호출 하면 동일한 요소 Seed가 생성 될 수 있습니다 Random. Random사용할 클래스 수준 을 만드는 것이 좋습니다 .

요약하면

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() 복잡성

HashSet<T>인덱스 별 조회를 지원하지 않으므로 ElementAt요청 된 요소에 도달 할 때까지 반복해야합니다. O (1)이 아닌 O (n) 단계가 필요합니다.