re:re:actable
Урок 034 минуты чтения

Как выбирать структуру данных под задачу?

На этой странице
Кратко

Структуру данных выбирают не по названию задачи, а по операциям, которые нужно делать быстро: поиск, вставка, удаление, порядок, минимум/максимум, соседство, префиксы или компоненты связности.

Вопрос

Как выбирать структуру данных под алгоритмическую задачу?

Главная идея

Сначала спроси:

Какая операция повторяется чаще всего?

Если ты много раз проверяешь "есть ли элемент", нужен Set.

Если ты много раз хранишь "значение -> индекс/частота", нужен Map.

Если нужен последний добавленный элемент, нужен Stack.

Если нужен первый добавленный элемент, нужна Queue.

Если нужен минимум/максимум, нужен Heap.

Таблица выбора

Признак задачиЧто рассмотреть
Нужно быстро проверить наличиеSet
Нужно хранить key -> valueMap
Нужно считать частотыMap
Нужно помнить индексыMap
Нужно работать с последним открытым элементомStack
Нужно обходить слоямиQueue + BFS
Нужен минимум/максимум каждый шагHeap / priority queue
Есть зависимостиGraph + topological sort
Есть связи "объединить группы"DSU / Union Find
Есть префиксы строкTrie
Есть диапазоны и суммыPrefix sums
Есть contiguous subarraySliding window
Есть отсортированный массивBinary search / two pointers
Есть grid/matrixBFS/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.

Документация

Big-O Cheat Sheet: Data Structures.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам