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

평균 시간 복잡 도 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 () 방식 으로 무 작위 수 를 얻 는 것 도 있 으 니, 여기 서 자세히 말 하지 않 겠 습 니 다.