평균 O(1) 시간에 다음 작업을 모두 지원하는 데이터 구조가 있다고 가정합니다.
-
insert(val) - 이미 존재하지 않는 경우 항목 val을 세트에 삽입합니다.
-
remove(val) - 존재하는 경우 세트에서 항목 val을 제거합니다.
-
getRandom - 현재 요소 집합에서 임의의 요소를 반환합니다. 각 요소는 반환될 확률이 같아야 합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
초기화를 위해 부모 맵과 요소 배열을 정의합니다.
-
insert() 함수의 경우 val을 입력으로 사용합니다.
-
val이 부모 맵에 없거나 parent[val] =0이면 요소에 val을 삽입하고 parent[val] :=1로 설정하고 true를 반환합니다.
-
-
거짓을 반환
-
remove() 메서드의 경우 제거하는 데 val이 필요합니다.
-
val이 부모 맵에 없거나 parent[val] =0이면 false를 반환합니다.
-
부모[val] 설정 :=0
-
index :=요소 배열의 val 인덱스
-
인덱스가 요소의 길이와 같지 않은 경우 – 1
-
temp :=요소의 마지막 요소
-
요소의 마지막 요소 설정 :=val
-
요소 설정[인덱스] :=임시
-
-
요소의 마지막 요소 삭제
-
getRandom() 메서드는 요소 배열에 있는 임의의 값을 반환합니다.
예시(파이썬)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
임포트 randomclass RandomizedSet(object):def __init__(self):self.present ={} self.elements =[] def insert(self, val):val이 self.present 또는 self.present[val]에 없는 경우 ==0:self.elements.append(val) self.present[val] =1 return True return False def remove(self, val):val이 self.present 또는 self.present[val]에 없는 경우 ==0:return False self.present[val] =0 index =self.elements.index(val) if index!=len(self.elements)-1:temp =self.elements[-1] self.elements[-1] =val self.elements[index]=temp self.elements.pop() return True def getRandom(self):return random.choice(self.elements)ob =RandomizedSet()print(ob.insert(1))print(ob .remove(2))print(ob.insert(2))print(ob.getRandom())print(ob.remove(1))print(ob.insert(2))print(ob.getRandom()) 입력
클래스를 초기화한 다음, insert(), remove(), getRandom() 함수를 호출합니다. 구현을 참조하십시오.
출력
TrueFalseTrue2TrueFalse2