380. Insert Delete GetRandom O(1)
leetcode medium
Task
Реализуйте класс RandomizedSet:
RandomizedSet(): Инициализирует объект RandomizedSet.
bool insert(int val): Вставляет элемент val в множество, если его там нет. Возвращает true, если элемент отсутствовал, и false в противном случае.
bool remove(int val): Удаляет элемент val из множества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае.
int getRandom(): Возвращает случайный элемент из текущего множества элементов (гарантируется, что по крайней мере один элемент существует при вызове этого метода). Каждый элемент должен иметь равную вероятность быть возвращенным.
Вы должны реализовать функции класса таким образом, чтобы каждая функция работала в среднем за O(1) по времени.
Пример:
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
C# solution
matched/originalusing System;
using System.Collections.Generic;
public class RandomizedSet {
private Dictionary<int, int> dict;
private List<int> list;
private Random rand;
public RandomizedSet() {
dict = new Dictionary<int, int>();
list = new List<int>();
rand = new Random();
}
public bool Insert(int val) {
if (dict.ContainsKey(val)) {
return false;
}
dict[val] = list.Count;
list.Add(val);
return true;
}
public bool Remove(int val) {
if (!dict.ContainsKey(val)) {
return false;
}
int index = dict[val];
int lastElement = list[list.Count - 1];
list[index] = lastElement;
dict[lastElement] = index;
list.RemoveAt(list.Count - 1);
dict.Remove(val);
return true;
}
public int GetRandom() {
return list[rand.Next(list.Count)];
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class RandomizedSet {
private unordered_map<int, int> dict;
private List<int> list;
private Random rand;
public RandomizedSet() {
dict = new unordered_map<int, int>();
list = new List<int>();
rand = new Random();
}
public bool Insert(int val) {
if (dict.count(val)) {
return false;
}
dict[val] = list.size();
list.push_back(val);
return true;
}
public bool Remove(int val) {
if (!dict.count(val)) {
return false;
}
int index = dict[val];
int lastElement = list[list.size() - 1];
list[index] = lastElement;
dict[lastElement] = index;
list.RemoveAt(list.size() - 1);
dict.Remove(val);
return true;
}
public int GetRandom() {
return list[rand.Next(list.size())];
}
}Java solution
matched/originalimport java.util.*;
public class RandomizedSet {
private Map<Integer, Integer> dict;
private List<Integer> list;
private Random rand;
public RandomizedSet() {
dict = new HashMap<>();
list = new ArrayList<>();
rand = new Random();
}
public boolean insert(int val) {
if (dict.containsKey(val)) {
return false;
}
dict.put(val, list.size());
list.add(val);
return true;
}
public boolean remove(int val) {
if (!dict.containsKey(val)) {
return false;
}
int index = dict.get(val);
int lastElement = list.get(list.size() - 1);
list.set(index, lastElement);
dict.put(lastElement, index);
list.remove(list.size() - 1);
dict.remove(val);
return true;
}
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}JavaScript solution
matched/originalclass RandomizedSet {
constructor() {
this.dict = new Map();
this.list = [];
}
insert(val) {
if (this.dict.has(val)) {
return false;
}
this.dict.set(val, this.list.length);
this.list.push(val);
return true;
}
remove(val) {
if (!this.dict.has(val)) {
return false;
}
const index = this.dict.get(val);
const lastElement = this.list.pop();
if (index < this.list.length) {
this.list[index] = lastElement;
this.dict.set(lastElement, index);
}
this.dict.delete(val);
return true;
}
getRandom() {
return this.list[Math.floor(Math.random() * this.list.length)];
}
}Python solution
matched/originalimport random
class RandomizedSet:
def __init__(self):
self.dict = {}
self.list = []
def insert(self, val: int) -> bool:
if val in self.dict:
return False
self.dict[val] = len(self.list)
self.list.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.dict:
return False
last_element = self.list[-1]
index = self.dict[val]
self.list[index] = last_element
self.dict[last_element] = index
self.list.pop()
del self.dict[val]
return True
def getRandom(self) -> int:
return random.choice(self.list)Go solution
matched/originalpackage main
import (
"math/rand"
"time"
)
type RandomizedSet struct {
dict map[int]int
list []int
}
func Constructor() RandomizedSet {
rand.Seed(time.Now().UnixNano())
return RandomizedSet{
dict: make(map[int]int),
list: make([]int, 0),
}
}
func (this *RandomizedSet) Insert(val int) bool {
if _, exists := this.dict[val]; exists {
return false
}
this.dict[val] = len(this.list)
this.list = append(this.list, val)
return true
}
func (this *RandomizedSet) Remove(val int) bool {
index, exists := this.dict[val]
if !exists {
return false
}
lastElement := this.list[len(this.list)-1]
this.list[index] = lastElement
this.dict[lastElement] = index
this.list = this.list[:len(this.list)-1]
delete(this.dict, val)
return true
}
func (this *RandomizedSet) GetRandom() int {
return this.list[rand.Intn(len(this.list))]
}Explanation
Algorithm
Создать словарь для хранения значений и их индексов, а также список для хранения значений.
Метод insert(val): Проверить наличие значения в словаре. Если отсутствует, добавить значение в список и обновить словарь с новым индексом.
Метод remove(val): Проверить наличие значения в словаре. Если присутствует, заменить удаляемое значение последним элементом списка, обновить его индекс в словаре, удалить последний элемент из списка и удалить значение из словаря.
Метод getRandom(): Возвращать случайный элемент из списка, используя встроенную функцию генерации случайных чисел.
😎