Форум программистов, компьютерный форум, киберфорум
alhaos
Войти
Регистрация
Восстановить пароль
Рейтинг: 5.00. Голосов: 1.

[golang] 380. Insert Delete GetRandom O(1)

Запись от alhaos размещена 04.02.2025 в 08:55. Обновил(-а) alhaos 04.02.2025 в 08:57
Показов 1484 Комментарии 0
Метки go, problem

Тут требуется реализовать структуру которая обслуживает список уникальных элементов и реализует следующий интерфейс:

Go
1
2
3
4
5
6
7
8
9
10
11
12
type RandomizedSet interface {
 // Insert Добавляет элемент к списку уникальных элементов
 // в случае успеха возвращает ИСТИНУ
 // в обратном случае ЛОЖЬ
 Insert(val int) bool
 // Remove Удаляет элемент из списка уникальных элементов
 // в случае успеха возвращает ИСТИНУ
 // в обратном случае ЛОЖЬ
 Remove(val int) bool
 // GetRandom Возвращает случайный элемент из списка
 GetRandom() int
}
Требуемая сложность O(1)

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

Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
// RandomizedSet 380. Insert Delete GetRandom O(1)
// Implement the RandomizedSet class:
// 
// RandomizedSet() Initializes the RandomizedSet object.
// bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
// bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
// int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
// You must implement the functions of the class such that each function works in average O(1) time complexity.
// 
// Example 1:
// 
// Input
// ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
// [[], [1], [2], [2], [], [1], [2], []]
// Output
// [null, true, false, true, 2, true, false, 2]
// 
// Explanation
// RandomizedSet randomizedSet = new RandomizedSet();
// randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
// randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
// randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
// randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
// randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
// randomizedSet.insert(2); // 2 was already in the set, so return false.
// randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
// 
// Constraints:
// 
// -231 <= val <= 231 - 1
// At most 2 * 105 calls will be made to insert, remove, and getRandom.
// There will be at least one element in the data structure when getRandom is called.
 
// RandomizedSet структура содержащая данные
type RandomizedSet struct {
    elements        []int       // слайс элементов
    elementIndexMap map[int]int // карта содержащая значение элемента и массив элемента
}
 
// Constructor конструктор для структуры RandomizedSet
func Constructor() RandomizedSet {
    // Вернуть RandomizedSet
    return RandomizedSet{
        elements:        []int{},           // Поле elements инициировать пустым слайсом целочисленных элементов
        elementIndexMap: make(map[int]int), // Создать пустую карту
    }
}
 
// Insert вставляет элемент при отсутствии данного элемента
// Возвращает ИСТИНУ в случае успеха, ЛОЖЬ в противоположном
func (this *RandomizedSet) Insert(val int) bool {
 
    // Инициировать exist бинарным признаком наличия элемента в карте элементов
    _, exist := this.elementIndexMap[val]
    // В случае наличия элемента
    if exist {
        // Вернуть ЛОЖЬ
        return false
    }
 
    // Добавить элемент в слайс элементов
    this.elements = append(this.elements, val)
 
    // Добавить элемент в карту индексов элементов
    this.elementIndexMap[val] = len(this.elements) - 1
 
    // Вернуть ИСТИНУ
    return true
}
 
// Remove удаляет элемент при наличии данного элемента
// Возвращает ИСТИНУ в случае успеха, ЛОЖЬ в противоположном
func (this *RandomizedSet) Remove(val int) bool {
 
    // Инициировать exist бинарным признаком наличия элемента в карте элементов
    _, exist := this.elementIndexMap[val]
    // В случае отсутствия элемента
    if !exist {
        // Вернуть ЛОЖЬ
        return false
    }
 
    // Определить индекс элемента по карте
    index := this.elementIndexMap[val]
 
    // Заменить значение элемента с индексом index на значение крайнего элемента в слайсе элементов
    this.elements[index] = this.elements[len(this.elements)-1]
 
    // Заменить значение индекса, нового значения элемента в карте индексов элементов
    this.elementIndexMap[this.elements[index]] = index
 
    // Переопределить слайс элементов им же без крайнего элемента
    this.elements = this.elements[:len(this.elements)-1]
 
    // Удалить элемент из карты элементов
    delete(this.elementIndexMap, val)
 
    // Вернуть ИСТИНУ
    return true
}
 
// GetRandom возвращает случайный элемент
func (this *RandomizedSet) GetRandom() int {
    // Проверить наличие элементов в слайсе
    if len(this.elements) == 0 {
        // Вернуть ноль
        return 0
    }
    // Получить индекс случайного элемента
    index := rand.Intn(len(this.elements))
 
    // Вернуть значение случайного элемента
    return this.elements[index]
}
https://github.com/alhaos/problems
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 0
Комментарии
 
Новые блоги и статьи
Ключевые слова Python
hw_wired 15.02.2025
Ключевые слова в Python - это специальные зарезервированные слова, которые имеют особое значение и функции в языке. В настоящее время Python включает 35 ключевых слов и 4 мягких ключевых слова. Эти. . .
Отличия изменяемых и неизменяемых типов в Python
hw_wired 15.02.2025
В Python существует принципиальное различие между изменяемыми (mutable) и неизменяемыми (immutable) типами данных, которое оказывает существенное влияние на работу программ. Это различие часто. . .
Python: сравнение списков и кортежей
hw_wired 15.02.2025
В Python последовательности являются одними из самых важных и часто используемых типов данных. Они позволяют хранить упорядоченные наборы элементов, к которым можно обращаться по индексу. Среди всех. . .
Как скачивать файлы с URL с помощью Python
hw_wired 15.02.2025
Для скачивания файлов Python предлагает как встроенные средства, так и сторонние библиотеки. Встроенный модуль urllib из стандартной библиотеки обеспечивает базовую функциональность для работы с URL. . .
Использование SQLAlchemy в Python
hw_wired 15.02.2025
SQLAlchemy - мощная библиотека для работы с базами данных в Python, которая предоставляет полноценный набор средств для объектно-реляционного отображения (ORM) и обширные возможности для работы с. . .
Взаимодействие с REST API в Python
hw_wired 15.02.2025
В современном мире разработки программного обеспечения REST API стал неотъемлемой частью архитектуры веб-приложений. API (Application Programming Interface) - это набор правил и протоколов,. . .
Разделение строк в Python
hw_wired 15.02.2025
Python предлагает богатый набор возможностей для работы со строками, и среди них разделение строк занимает особое место. Этот процесс позволяет разбивать текст на отдельные компоненты, что критично. . .
Объединение строк в Python
hw_wired 15.02.2025
При работе с текстовыми данными в Python нередко возникает необходимость объединять несколько строк в одну. Это может потребоваться при форматировании вывода, обработке текстовых файлов или создании. . .
Лучшие игровые движки на Python
hw_wired 15.02.2025
В последнее время разработка игр стала одним из самых популярных направлений программирования, и Python не остался в стороне от этого тренда. Несмотря на то, что Python обычно не ассоциируется с. . .
Декоратор jit в Python
hw_wired 15.02.2025
Если вы достаточно долго изучаете программы и пакеты на Python для машинного обучения, то наверняка замечали, что паттерн "JIT-декоратор" довольно популярен. Этот подход позволяет превратить обычные. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru