삽입 삭제 GetRandom O(1) - 중복 허용

RandomizedCollection 중복 가능성이 있는 숫자 모음(즉, 다중 집합)을 포함하는 데이터 구조입니다. 특정 요소를 삽입 및 제거하고 임의의 요소를 제거하는 것도 지원해야 합니다.

구현 RandomizedCollection 수업:

RandomizedCollection() 빈 RandomizedCollection를 초기화합니다. 물체.

bool insert(int val) 항목 삽입 val 항목이 이미 있는 경우에도 다중 집합으로. 반품 true 항목이 없으면 false 그렇지 않으면.

bool remove(int val) 항목을 제거합니다 val 존재하는 경우 다중 세트에서. 반품 true 항목이 있으면 false 그렇지 않으면. val multiset에서 여러 번 발생하면 그중 하나만 제거합니다.

int getRandom() 요소의 현재 다중 집합에서 임의의 요소를 반환합니다. 반환되는 각 요소의 확률은 다중 집합에 포함된 동일한 값의 수와 선형적으로 관련됩니다.

각 기능이 평균적으로 작동하도록 클래스의 기능을 구현해야 합니다 O(1) 시간 복잡도.

참고: 테스트 케이스는 getRandom RandomizedCollection에 적어도 하나의 항목이 있는 경우에만 호출됩니다. .

예 1:

입력
["RandomizedCollection", "삽입", "삽입", "삽입", "getRandom", "제거", "getRandom"]
[[], [1], [1], [2], [], [1], []]
산출
[널, 참, 거짓, 참, 2, 참, 1]

설명
RandomizedCollection randomizedCollection = new RandomizedCollection();
randomizedCollection.insert(1);//컬렉션에 1이 포함되어 있지 않으므로 true를 반환합니다.
//컬렉션에 1을 삽입합니다.
randomizedCollection.insert(1);//컬렉션에 1이 포함되어 있으므로 false를 반환합니다.
//컬렉션에 다른 1을 삽입합니다. 컬렉션에는 이제 [1,1]이 포함됩니다.
randomizedCollection.insert(2);//컬렉션에 2가 포함되어 있지 않으므로 true를 반환합니다.
//컬렉션에 2를 삽입합니다. 컬렉션에는 이제 [1,1,2]가 포함됩니다.
randomizedCollection.getRandom();//getRandom은 다음을 수행해야 합니다.
//- 2/3의 확률로 1을 반환하거나
//- 1/3의 확률로 2를 반환합니다.
randomizedCollection.remove(1);//컬렉션에 1이 포함되어 있으므로 true를 반환합니다.
//컬렉션에서 1을 제거합니다. 컬렉션에는 이제 [1,2]가 포함됩니다.
randomizedCollection.getRandom();//getRandom은 1 또는 2를 반환해야 하며 둘 다 가능성이 동일합니다.

제약:

-231 <= val <= 231 - 1

기껏해야 2 * 105 총 호출은 insert , remove , 및 getRandom .

getRandom 호출됩니다.

해결책:

import bisect
import random

class RandomizedCollection:

    def __init__(self):
        self.items = []

    def exists(self, val):
        i = bisect.bisect_left(self.items, val)
        return i < len(self.items) and self.items[i] == val

    def insert(self, val: int) -> bool:
        if not self.exists(val):
            bisect.insort(self.items, val)
            return True
        bisect.insort(self.items, val)
        return False

    def remove(self, val: int) -> bool:
        if self.exists(val):
            del self.items[bisect.bisect_left(self.items, val)]
            return True
        return False

    def getRandom(self) -> int:
        return random.choice(self.items)


# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()