Структура для хранения уникальных значений

Средняя

medium

18 December 2023

Описание задачи #

Реализуйте структуру данных для управления числами, которая имплементируют следующие методы:

Insert — добавляет новый элемент в структуру без создания дубликатов.
Remove — удаляет выбранный элемент из массива.
GetRandom — возвращает случайного элемент из ранее добавленных с равной вероятностью.

Ограничения #

Все методы должны работать с константной сложностью по времени — O(1).

Примеры #

Добавление значений в структуру.

    const store = new Store()

    store.insert(1)
    store.insert(2)
    store.insert(3)
    store.insert(2)

    // values — 1, 2, 3

Удаление значений из структуры.

    const store = new Store()

    store.insert(1)
    store.insert(2)
    store.insert(3)
    store.remove(2)

    // values — 1, 3

Получение случайного значения из структуры.

    const store = new Store()

    store.insert(1)
    store.insert(2)
    store.insert(3)
    
    const value = store.getRandom()

    // value — 1 (or 2 or 3 with equal probability)

Решение #

В первую очередь возникает идея использования структуры данных на основе хэш-таблицы, поскольку она по умолчанию обеспечивает добавление только уникальных значений. Кроме того, операции вставки и удаления из хэш-таблицы занимают константное время, что соответствует нашим требованиям. Однако для получения случайного значения потребуется преобразовать все значения в массив и затем выбрать произвольный индекс в массиве, что приведет к линейной сложности из-за дополнительного преобразования в массив.

С другой стороны, возможно хранение данных в массиве. Это облегчит получение случайного значения, но усложнит операции добавления и удаления элементов.

При добавлении нового элемента в массив потребуется проверка наличия дубликатов, что также займет линейное время.
При удалении элемента из середины массива потребуется сдвиг влево всего его хвоста на одну позицию, что также займет линейное время.

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

Для хранения значений мы будем использовать массив values. Кроме этого мы заведем хеш-таблицу indexesMap для хранения индексов каждого элемента в массиве. В качестве ключа — число, в качестве значения — его индекс в массиве.

Теперь определим логику работы каждого метода структуры данных.

Insert #

При добавлении нового элемента мы сначала проверяем существует ли он в хеш-таблице. Если элемента в ней нет, то добавляем его сначала в массив, а потом в таблицу. Это позволяет нам избежать добавления дубликатов.

Remove #

При удалении элемента из массива сначала проверяем есть ли он в хеш-таблице. Если элемент в ней не присутствует, то мы просто заканчиваем выполнение функции.

Нам необходимо удалить элемент из массива, но сделать это за константное время можно только когда удаляется последний элемент. Так как нам не нужно сохранять порядок вставки мы можем получить индекс элемента в массиве из хеш-таблицы и поменять его местами с последним элементом. Последний же элемент после перестановки можно удалить. Также нужно удалить элемент из таблицы.

GetRandom #

Для получения случайного элемента из массива, необходимо создать генератор случайных чисел от 0 до индекса последнего элемента в массиве. После получения случайного числа достаточно вернуть значение, которое находится в массиве под этим индексом.

package unique_value_structure

import (
	"math/rand"
)

type Store struct {
	indexesMap map[int]int
	values     []int
}

func New() *Store {
	return &Store{
		indexesMap: make(map[int]int),
		values:     make([]int, 0),
	}
}

func (s *Store) Insert(value int) {
	_, exists := s.indexesMap[value]
	if exists {
		return
	}

	s.values = append(s.values, value)
	s.indexesMap[value] = len(s.values) - 1
}

func (s *Store) Remove(value int) {
	index, exists := s.indexesMap[value]
	if !exists {
		return
	}

	last := s.values[len(s.values)-1]
	s.values[index] = last
	s.indexesMap[last] = index

	s.values = s.values[:len(s.values)-1]
	delete(s.indexesMap, value)
}

func (s *Store) GetRandom() int {
	index := rand.Intn(len(s.values))
	return s.values[index]
}

// Method for tests
func (s *Store) getValues() []int {
	return s.values
}

export class Store {
    private indexesMap: Map<number, number>
    private values: number[]

    constructor() {
        this.indexesMap = new Map()
        this.values = []
    }

    insert(value: number) {
        if (this.indexesMap.has(value)) {
            return
        }

        this.values.push(value)
        this.indexesMap.set(value, this.values.length - 1)
    }

    remove(value: number) {
        const index = this.indexesMap.get(value)
        if (!index) {
            return
        }

        const last = this.values.pop()
        if (!last) {
            return;
        }

        this.values[index] = last
        this.indexesMap.set(last, index)

        this.indexesMap.delete(value)
    }

    getRandom(): number {
        return this.values[Math.floor(Math.random() * this.values.length)]
    }

    // Method for tests
    getValues(): number[] {
        return this.values
    }
}

Оценка сложности #

По времени

Все методы реализованы так, чтобы иметь константную сложность по времени O(1) согласно условиям задачи.

По памяти

Для хранения данных в структуре мы используем массив и дублирующую хеш-мапу, из-за этого суммарная сложность — O(2n). Итоговая сложность по времени линейная — O(n), так как множитель 2 можно опустить.

Хак в GO #

Решение выше по факту является универсальным, и применимо ко всем языкам. Однако, в некоторых языках есть свои особенности, которые могут упростить решение задачи.

В частности, особенностью Go Lang является тот факт, что хеш таблица в нем не гарантирует порядок вывода ключей. Более того, ключи при выводе определяются случайным образом. Говорят, таким образом разработчики языка стимулируют других разработчиков не завязываться на порядок ключей в хеш-таблицах.

Все это означает, что в Go мы сможем реализовать необходимую структуру данных, используя только Map.

package unique_value_structure

type Store struct {
	values map[int]bool
}

func New() *Store {
	return &Store{
		values: make(map[int]bool),
	}
}

func (s *Store) Insert(value int) {
	s.values[value] = true
}

func (s *Store) Remove(value int) {
	delete(s.values, value)
}

func (s *Store) GetRandom() int {
	for val := range s.values {
		return val
	}
	return 0
}

Algorithmics