Frequency map

От /

Frequency map — это словарь частот: структура данных, где мы храним,
сколько раз каждый элемент встретился.

То есть не просто список значений:

[a, b, a, c, b, a]

а карта частот:

a -> 3
b -> 2
c -> 1

По сути:

freq = {}

for x in arr:
    freq[x] = freq.get(x, 0) + 1

Frequency map нужна, когда задача не про порядок элементов, а про количество
появлений.

Например, вместо того чтобы каждый раз искать элемент в массиве заново, мы один
раз считаем частоты, а потом быстро проверяем нужные значения в hash map.

1. Найти дубликаты

Есть массив:

[1, 2, 3, 2, 4, 1]

Frequency map:

1 -> 2
2 -> 2
3 -> 1
4 -> 1

Значит 1 и 2 встречаются больше одного раза.

На JavaScript:

const nums = [1, 2, 3, 2, 4, 1];
const freq = new Map();

for (const num of nums) {
  freq.set(num, (freq.get(num) || 0) + 1);
}

const duplicates = [];

for (const [num, count] of freq) {
  if (count > 1) {
    duplicates.push(num);
  }
}

console.log(duplicates); // [1, 2]

2. Проверить анаграммы

Например:

"listen"
"silent"

Если у двух строк одинаковая frequency map по буквам, значит они анаграммы.

l -> 1
i -> 1
s -> 1
t -> 1
e -> 1
n -> 1

Идея:

function buildFrequencyMap(str) {
  const freq = new Map();

  for (const ch of str) {
    freq.set(ch, (freq.get(ch) || 0) + 1);
  }

  return freq;
}

function areAnagrams(a, b) {
  if (a.length !== b.length) {
    return false;
  }

  const freqA = buildFrequencyMap(a);
  const freqB = buildFrequencyMap(b);

  if (freqA.size !== freqB.size) {
    return false;
  }

  for (const [ch, count] of freqA) {
    if (freqB.get(ch) !== count) {
      return false;
    }
  }

  return true;
}

console.log(areAnagrams("listen", "silent")); // true

3. Найти most frequent element

Например:

[4, 4, 1, 2, 4, 2]

Frequency map:

4 -> 3
2 -> 2
1 -> 1

Самый частый элемент — 4.

const nums = [4, 4, 1, 2, 4, 2];
const freq = new Map();

for (const num of nums) {
  freq.set(num, (freq.get(num) || 0) + 1);
}

let mostFrequent = null;
let bestCount = 0;

for (const [num, count] of freq) {
  if (count > bestCount) {
    mostFrequent = num;
    bestCount = count;
  }
}

console.log(mostFrequent); // 4

В каких структурах это обычно делается

В Java:

Map<Integer, Integer> freq = new HashMap<>();

for (int num : nums) {
    freq.put(num, freq.getOrDefault(num, 0) + 1);
}

В Python:

from collections import Counter

freq = Counter(nums)

В JavaScript:

const freq = new Map();

for (const x of arr) {
  freq.set(x, (freq.get(x) || 0) + 1);
}

Сложность

Построение frequency map обычно занимает:

Time:  O(n)
Space: O(k)

где n — количество элементов во входных данных, а k — количество уникальных
элементов.

Если все элементы разные, k = n. Если уникальных элементов мало, памяти нужно
меньше.

Главная идея

frequency map — это не отдельный сложный алгоритм, а приём:

превратить поток, массив или строку в карту вида
элемент -> сколько раз встретился

И дальше уже на этой карте решать задачу.

Часто это даёт переход от простого двойного цикла O(n^2) к нормальному O(n),
потому что вместо постоянного поиска по массиву мы один раз считаем частоты, а
потом быстро смотрим значения в hash map.

Subscribe
Прокрутить вверх