380. 상수 시간 삽입, 삭제, 랜 덤 요소 가 져 오기
3588 단어 Leetcode
예시:
// 。
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 () 방식 으로 무 작위 수 를 얻 는 것 도 있 으 니, 여기 서 자세히 말 하지 않 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 문제풀이 노트 113.경로 총 II경로 총 II 제목 요구 사항 문제풀이 두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다. 설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다. 예: 다음과 같은 두 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.