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

type RandomizedSet interface {
 // Insert Добавляет элемент к списку уникальных элементов
 // в случае успеха возвращает ИСТИНУ
 // в обратном случае ЛОЖЬ
 Insert(val int) bool
 // Remove Удаляет элемент из списка уникальных элементов
 // в случае успеха возвращает ИСТИНУ
 // в обратном случае ЛОЖЬ
 Remove(val int) bool
 // GetRandom Возвращает случайный элемент из списка
 GetRandom() int
}

// [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]
}