381. Insert Delete GetRandom O(1) - Duplicates allowed

LeetCode hard оригинал: C# #backtracking #csharp #design #hard #hash-table #leetcode

LeetCode Static

RandomizedCollection — это структура данных, содержащая набор чисел, возможно с дубликатами (т.е. мультимножество). Она должна поддерживать вставку и удаление определенных элементов, а также предоставление случайного элемента.

Реализуйте класс RandomizedCollection:

RandomizedCollection(): Инициализирует пустой объект RandomizedCollection.

bool insert(int val): Вставляет элемент val в мультимножество, даже если элемент уже присутствует. Возвращает true, если элемента не было, и false в противном случае.

bool remove(int val): Удаляет элемент val из мультимножества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. Если у val несколько вхождений в мультимножестве, удаляется только одно из них.

int getRandom(): Возвращает случайный элемент из текущего мультимножества. Вероятность возврата каждого элемента пропорциональна числу вхождений этого элемента в мультимножество.

Реализуйте функции класса так, чтобы каждая функция работала в среднем за O(1) времени.

Пример:

Input

["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]

[[], [1], [1], [2], [], [1], []]

Output

[null, true, false, true, 2, true, 1]

C# решение

сопоставлено/оригинал

using System;
using System.Collections.Generic;
public class RandomizedCollection {
    private Dictionary<int, HashSet<int>> dict;
    private List<int> list;
    private Random rand;
    public RandomizedCollection() {
        dict = new Dictionary<int, HashSet<int>>();
        list = new List<int>();
        rand = new Random();
    }
    public bool Insert(int val) {
        bool exists = dict.ContainsKey(val);
        if (!exists) {
            dict[val] = new HashSet<int>();
        }
        dict[val].Add(list.Count);
        list.Add(val);
        return !exists;
    }
    public bool Remove(int val) {
        if (!dict.ContainsKey(val) || dict[val].Count == 0) {
            return false;
        }
        int index = dict[val].First();
        dict[val].Remove(index);
        int lastElement = list[list.Count - 1];
        list[index] = lastElement;
        dict[lastElement].Add(index);
        dict[lastElement].Remove(list.Count - 1);
        list.RemoveAt(list.Count - 1);
        if (dict[val].Count == 0) {
            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 RandomizedCollection {
    private unordered_map<int, HashSet<int>> dict;
    private List<int> list;
    private Random rand;
    public RandomizedCollection() {
        dict = new unordered_map<int, HashSet<int>>();
        list = new List<int>();
        rand = new Random();
    }
    public bool Insert(int val) {
        bool exists = dict.count(val);
        if (!exists) {
            dict[val] = new HashSet<int>();
        }
        dict[val].push_back(list.size());
        list.push_back(val);
        return !exists;
    }
    public bool Remove(int val) {
        if (!dict.count(val) || dict[val].size() == 0) {
            return false;
        }
        int index = dict[val].First();
        dict[val].Remove(index);
        int lastElement = list[list.size() - 1];
        list[index] = lastElement;
        dict[lastElement].push_back(index);
        dict[lastElement].Remove(list.size() - 1);
        list.RemoveAt(list.size() - 1);
        if (dict[val].size() == 0) {
            dict.Remove(val);
        }
        return true;
    }
    public int GetRandom() {
        return list[rand.Next(list.size())];
    }
}

Java решение

сопоставлено/оригинал

import java.util.*;

public class RandomizedCollection {
    private Map<Integer, Set<Integer>> dict;
    private List<Integer> list;
    private Random rand;

    public RandomizedCollection() {
        dict = new HashMap<>();
        list = new ArrayList<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        boolean exists = dict.containsKey(val);
        if (!exists) {
            dict.put(val, new HashSet<>());
        }
        dict.get(val).add(list.size());
        list.add(val);
        return !exists;
    }

    public boolean remove(int val) {
        if (!dict.containsKey(val) || dict.get(val).isEmpty()) {
            return false;
        }
        int index = dict.get(val).iterator().next();
        dict.get(val).remove(index);
        int lastElement = list.get(list.size() - 1);
        list.set(index, lastElement);
        dict.get(lastElement).add(index);
        dict.get(lastElement).remove(list.size() - 1);
        list.remove(list.size() - 1);
        if (dict.get(val).isEmpty()) {
            dict.remove(val);
        }
        return true;
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

JavaScript решение

сопоставлено/оригинал

class RandomizedCollection {
    constructor() {
        this.dict = new Map();
        this.list = [];
    }

    insert(val) {
        let exists = this.dict.has(val);
        if (!exists) {
            this.dict.set(val, new Set());
        }
        this.dict.get(val).add(this.list.length);
        this.list.push(val);
        return !exists;
    }

    remove(val) {
        if (!this.dict.has(val) || this.dict.get(val).size === 0) {
            return false;
        }
        let index = this.dict.get(val).values().next().value;
        this.dict.get(val).delete(index);
        let lastElement = this.list[this.list.length - 1];
        this.list[index] = lastElement;
        this.dict.get(lastElement).add(index);
        this.dict.get(lastElement).delete(this.list.length - 1);
        this.list.pop();
        if (this.dict.get(val).size === 0) {
            this.dict.delete(val);
        }
        return true;
    }

    getRandom() {
        return this.list[Math.floor(Math.random() * this.list.length)];
    }
}

Python решение

сопоставлено/оригинал

import random
from collections import defaultdict

class RandomizedCollection:
    def __init__(self):
        self.dict = defaultdict(set)
        self.list = []

    def insert(self, val: int) -> bool:
        self.dict[val].add(len(self.list))
        self.list.append(val)
        return len(self.dict[val]) == 1

    def remove(self, val: int) -> bool:
        if not self.dict[val]:
            return False
        index = self.dict[val].pop()
        last_element = self.list[-1]
        self.list[index] = last_element
        self.dict[last_element].add(index)
        self.dict[last_element].discard(len(self.list) - 1)
        self.list.pop()
        if not self.dict[val]:
            del self.dict[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.list)

Go решение

сопоставлено/оригинал

package main

import (
    "math/rand"
    "time"
)

type RandomizedCollection struct {
    dict map[int]map[int]struct{}
    list []int
}

func Constructor() RandomizedCollection {
    rand.Seed(time.Now().UnixNano())
    return RandomizedCollection{
        dict: make(map[int]map[int]struct{}),
        list: []int{},
    }
}

func (this *RandomizedCollection) Insert(val int) bool {
    _, exists := this.dict[val]
    if !exists {
        this.dict[val] = make(map[int]struct{})
    }
    this.dict[val][len(this.list)] = struct{}{}
    this.list = append(this.list, val)
    return !exists
}

func (this *RandomizedCollection) Remove(val int) bool {
    indices, exists := this.dict[val]
    if !exists || len(indices) == 0 {
        return false
    }
    var index int
    for k := range indices {
        index = k
        break
    }
    delete(this.dict[val], index)
    lastElement := this.list[len(this.list)-1]
    this.list[index] = lastElement
    this.dict[lastElement][index] = struct{}{}
    delete(this.dict[lastElement], len(this.list)-1)
    this.list = this.list[:len(this.list)-1]
    if len(this.dict[val]) == 0 {
        delete(this.dict, val)
    }
    return true
}

func (this *RandomizedCollection) GetRandom() int {
    return this.list[rand.Intn(len(this.list))]
}

Algorithm

Создать словарь для хранения значений и их индексов в списке, а также список для хранения всех элементов мультимножества.

Метод insert(val): Добавить значение в конец списка и обновить словарь, добавив индекс этого значения. Возвращать true, если значение отсутствовало ранее, и false в противном случае.

Метод remove(val): Удалить одно вхождение значения из словаря и списка. Для удаления значения заменить его последним элементом списка и обновить словарь. Возвращать true, если значение присутствовало, и false в противном случае.

Метод getRandom(): Возвращать случайный элемент из списка, обеспечивая равновероятное распределение на основе количества вхождений каждого элемента.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.