Как выбирать структуру данных под задачу?
На этой странице
Структуру данных выбирают не по названию задачи, а по операциям, которые нужно делать быстро: поиск, вставка, удаление, порядок, минимум/максимум, соседство, префиксы или компоненты связности.
Вопрос
Как выбирать структуру данных под алгоритмическую задачу?
Главная идея
Сначала спроси:
Какая операция повторяется чаще всего?Если ты много раз проверяешь "есть ли элемент", нужен Set.
Если ты много раз хранишь "значение -> индекс/частота", нужен Map.
Если нужен последний добавленный элемент, нужен Stack.
Если нужен первый добавленный элемент, нужна Queue.
Если нужен минимум/максимум, нужен Heap.
Таблица выбора
| Признак задачи | Что рассмотреть |
|---|---|
| Нужно быстро проверить наличие | Set |
| Нужно хранить key -> value | Map |
| Нужно считать частоты | Map |
| Нужно помнить индексы | Map |
| Нужно работать с последним открытым элементом | Stack |
| Нужно обходить слоями | Queue + BFS |
| Нужен минимум/максимум каждый шаг | Heap / priority queue |
| Есть зависимости | Graph + topological sort |
| Есть связи "объединить группы" | DSU / Union Find |
| Есть префиксы строк | Trie |
| Есть диапазоны и суммы | Prefix sums |
| Есть contiguous subarray | Sliding window |
| Есть отсортированный массив | Binary search / two pointers |
| Есть grid/matrix | BFS/DFS по координатам |
Array
Используй массив, если:
- нужен порядок;
- нужен доступ по индексу;
- нужно пройти все элементы;
- данные компактные и линейные.
for (let i = 0; i < nums.length; i++) {
// nums[i]
}Осторожно:
unshiftиshiftобычно дорогие;includesвнутри цикла может датьO(n^2);sortмутирует массив.
Set
Используй Set, если важен факт наличия.
function hasDuplicate(nums: number[]): boolean {
const seen = new Set<number>()
for (const num of nums) {
if (seen.has(num)) return true
seen.add(num)
}
return false
}Сигналы:
- "unique";
- "duplicate";
- "contains";
- "already seen";
- "visited".
Map
Используй Map, если нужно хранить данные по ключу.
function countChars(s: string): Map<string, number> {
const count = new Map<string, number>()
for (const char of s) {
count.set(char, (count.get(char) ?? 0) + 1)
}
return count
}Сигналы:
- частоты;
- индексы;
- groups;
- cache;
- memoization;
- mapping old -> new.
Stack
Stack нужен, когда важен последний незакрытый элемент.
function isValidParentheses(s: string): boolean {
const stack: string[] = []
const pairs = new Map([
[")", "("],
["]", "["],
["}", "{"],
])
for (const char of s) {
if (!pairs.has(char)) {
stack.push(char)
} else if (stack.pop() !== pairs.get(char)) {
return false
}
}
return stack.length === 0
}Сигналы:
- скобки;
- undo;
- nested structures;
- monotonic stack;
- DFS без рекурсии.
Queue
Queue нужна для BFS и обработки по порядку поступления.
const queue: number[] = [start]
let head = 0
while (head < queue.length) {
const node = queue[head++]
}В JS лучше не использовать shift() в большом цикле, потому что элементы массива сдвигаются.
Heap
Heap нужен, когда каждый шаг нужен текущий минимум или максимум.
Сигналы:
- top K;
- merge K sorted lists;
- Dijkstra;
- meeting rooms;
- median stream;
- scheduling.
Graph
Graph нужен, если задача про связи.
Сигналы:
- users connected;
- routes;
- dependencies;
- prerequisites;
- islands;
- network;
- parent-child не обязательно дерево.
Часто graph хранят как adjacency list:
const graph = new Map<string, string[]>()Как думать на задаче
Пример:
Нужно найти, есть ли в массиве два числа с суммой target.Операция:
для каждого числа проверить, было ли target - num раньшеСтруктура:
Map или SetЕсли нужны индексы - Map.
Если нужны только значения/факт - Set.
Что важно помнить: частые ошибки
- Использовать массив для поиска наличия и получить
O(n^2). - Использовать
Map, когда нужен толькоSet. - Использовать
Objectс ключами-объектами и получить не то поведение. - Использовать
shift()для очереди. - Брать heap, хотя можно отсортировать один раз.
- Не учитывать память структуры данных.
Что отвечать на собеседовании?
Я выбираю структуру данных по операции, которую нужно ускорить. Для наличия беру Set, для key-value и частот - Map, для вложенных/последних элементов - stack, для BFS - queue, для текущего минимума/максимума - heap, для связей - graph, для префиксов - trie, для объединения компонент - DSU. После выбора объясняю trade-off: быстрее по времени, но обычно больше памяти.
Мини-шпаргалка
- Наличие ->
Set. - Частоты/индексы ->
Map. - Последний открытый ->
Stack. - Слои/кратчайший путь без весов ->
Queue. - Min/max каждый шаг ->
Heap. - Связи ->
Graph. - Префиксы ->
Trie. - Объединение групп ->
DSU.