380. Insert Delete GetRandom O(1)
Реализуйте класс 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# решение
сопоставлено/оригиналusing 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++ решение
auto-draft, проверить перед отправкой#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 решение
сопоставлено/оригиналimport 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 решение
сопоставлено/оригиналclass 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 решение
сопоставлено/оригиналimport 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 решение
сопоставлено/оригиналpackage 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))]
}Algorithm
Создать словарь для хранения значений и их индексов, а также список для хранения значений.
Метод insert(val): Проверить наличие значения в словаре. Если отсутствует, добавить значение в список и обновить словарь с новым индексом.
Метод remove(val): Проверить наличие значения в словаре. Если присутствует, заменить удаляемое значение последним элементом списка, обновить его индекс в словаре, удалить последний элемент из списка и удалить значение из словаря.
Метод getRandom(): Возвращать случайный элемент из списка, используя встроенную функцию генерации случайных чисел.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.