Randomized Algorithms¶
Table of Contents¶
- 398. Random Pick Index (Medium)
- 382. Linked List Random Node (Medium)
- 384. Shuffle an Array (Medium)
- 470. Implement Rand10() Using Rand7() (Medium)
- 528. Random Pick with Weight (Medium)
- 710. Random Pick with Blacklist (Hard)
- 478. Generate Random Point in a Circle (Medium)
- 497. Random Point in Non-overlapping Rectangles (Medium)
- 519. Random Flip Matrix (Medium)
- 380. Insert Delete GetRandom O(1) (Medium)
- 381. Insert Delete GetRandom O(1) - Duplicates allowed (Hard)
- 1515. Best Position for a Service Centre (Hard)
- 1968. Array With Elements Not Equal to Average of Neighbors (Medium)
398. Random Pick Index¶
382. Linked List Random Node¶
384. Shuffle an Array¶
470. Implement Rand10() Using Rand7()¶
528. Random Pick with Weight¶
710. Random Pick with Blacklist¶
478. Generate Random Point in a Circle¶
497. Random Point in Non-overlapping Rectangles¶
-
Tags: Array, Math, Binary Search, Reservoir Sampling, Prefix Sum, Ordered Set, Randomized
519. Random Flip Matrix¶
380. Insert Delete GetRandom O(1)¶
import random
class RandomizedSet:
def __init__(self):
self.nums = []
self.pos = {} # num: idx
def insert(self, val: int) -> bool:
if val in self.pos:
return False
self.pos[val] = len(self.nums)
self.nums.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.pos:
return False
idx = self.pos[val]
last_val = self.nums[-1]
self.nums[idx] = last_val
self.pos[last_val] = idx
self.nums.pop()
del self.pos[val]
return True
def getRandom(self) -> int:
return random.choice(self.nums)
def test_RandomizedSet():
obj = RandomizedSet()
assert obj.insert(1)
assert not obj.remove(2)
assert obj.insert(2)
assert obj.getRandom() in [1, 2]
assert obj.remove(1)
assert not obj.insert(2)
assert obj.getRandom() == 2