380. 상수 시간 삽입, 삭제, 랜 덤 요소 가 져 오기

3588 단어 Leetcode
평균 시간 복잡 도 O (1) 다음 작업 을 수행 하 는 데이터 구조 입 니 다.
  • insert (val): 요소 val 이 존재 하지 않 을 때 집합 에 이 항목 을 삽입 합 니 다.
  • remove (val): 요소 val 이 존재 할 때 집합 에서 이 항목 을 제거 합 니 다.
  • getRandom: 기 존 집합 중 하 나 를 무 작위 로 되 돌려 줍 니 다.모든 요 소 는 같은 확률 로 되 돌아 와 야 한다.

  • 예시:
    //          。
    RandomizedSet randomSet = new RandomizedSet();
    
    //        1 。   true    1       。
    randomSet.insert(1);
    
    //    false ,         2 。
    randomSet.remove(2);
    
    //        2 。   true 。       [1,2] 。
    randomSet.insert(2);
    
    // getRandom       1   2 。
    randomSet.getRandom();
    
    //        1 ,   true 。       [2] 。
    randomSet.remove(1);
    
    // 2      ,     false 。
    randomSet.insert(2);
    
    //    2          ,getRandom      2 。
    randomSet.getRandom();
    

    사고 1: 먼저 생각 할 수 있 는 생각 은 사전 으로 실현 하고 d. get (key, 0) 을 통 해 val 요소 가 존재 하 는 지 여 부 를 판단 하지만 1664 ms 는 5.26%, 18 MB 를 넘 어 5.32% 를 넘는다.
    from random import choice
    class RandomizedSet:
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.nums = {}
    
        def insert(self, val: int) -> bool:
            """
            Inserts a value to the set. Returns true if the set did not already contain the specified element.
            """
            if self.nums.get(val, 0) == 0:
                self.nums[val] = 1
                return True
            return False
    
        def remove(self, val: int) -> bool:
            """
            Removes a value from the set. Returns true if the set contained the specified element.
            """
            if self.nums.get(val, 0) != 0:
                self.nums[val] = 0
                return True
            return False
    
        def getRandom(self) -> int:
            """
            Get a random element from the set.
            """
            keys = [key for key in self.nums.keys() if self.nums[key] == 1]
            return choice(keys)
    
    # Your RandomizedSet object will be instantiated and called as such:
    # obj = RandomizedSet()
    # param_1 = obj.insert(val)
    # param_2 = obj.remove(val)
    # param_3 = obj.getRandom()
    

    나중에 dict 가 요 소 를 삭제 하 는 동작 이 있다 는 것 을 알 게 되 었 습 니 다. 그래서 모든 insert 가 했 던 val 을 저장 할 필요 가 없습니다. 그러면 getRandom 에서 옮 겨 다 닐 필요 가 없습니다. 244 ms, 60.35%, 17.8 MB 를 초과 하고 5.32% 를 초과 합 니 다. 최 적 화 된 코드 는 다음 과 같 습 니 다.
    from random import choice
    class RandomizedSet:
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.nums = {}
    
        def insert(self, val: int) -> bool:
            """
            Inserts a value to the set. Returns true if the set did not already contain the specified element.
            """
            if val not in self.nums:
                self.nums[val] = 1
                return True
            return False
    
        def remove(self, val: int) -> bool:
            """
            Removes a value from the set. Returns true if the set contained the specified element.
            """
            if val in self.nums:
                self.nums.pop(val)
                return True
            return False
    
        def getRandom(self) -> int:
            """
            Get a random element from the set.
            """
            return choice(list(self.nums.keys()))
    
    # Your RandomizedSet object will be instantiated and called as such:
    # obj = RandomizedSet()
    # param_1 = obj.insert(val)
    # param_2 = obj.remove(val)
    # param_3 = obj.getRandom()
    

    문제 풀이 에는 set 의 실현 방식 도 있 고, 어떤 것 은 randint () 방식 으로 무 작위 수 를 얻 는 것 도 있 으 니, 여기 서 자세히 말 하지 않 겠 습 니 다.

    좋은 웹페이지 즐겨찾기