---
round: 3
ticket_no: 13
source_no: 24
slug: top-k-frequent-words
topic: Heap / Hash
difficulty: Medium
leetcode_id: 692
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 13 — Top K Frequent Words

## Условие (как предъявлено)

Дан массив строк `words` и целое число `k`. Верните `k` самых частых слов. Слова отсортированы по убыванию частоты. При одинаковой частоте слова упорядочены лексикографически.

```
Input:  words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]

Input:  words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output: ["the","is","sunny","day"]
```

Constraints: `1 <= words.length <= 500`; `1 <= words[i].length <= 10`; `words[i]` состоит из строчных английских букв; `1 <= k <= количество уникальных слов`.

## Ответ

> Здесь можно два решения рассмотреть. Первое — это пройтись и составить хэш, ключами которого являются слова, а значением является счётчик, сколько раз они встретились. Вот. Дальше нужно отсортировать элементы этого хэша по ну, при к, в общем, отсортировать по двум значениям. Да, то есть, надо отсортировать по этому числу вхождений, и второй признак — это лексиграфический. Вот, и выдать два элемента. Второй вариант — можно построить кучу, которая будет сортироваться как раз тоже по этому правилу сравнения: что самое топовое слово будет наверху. То есть, получается, мы, когда прошли весь массив наверху, просто берём последних топовых элементов. То есть, по факту, мы к раз должны достать голову. Куча должна быть соответственно уже представлена. И это сравнение туда должно быть передано.

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

**Критерии:** идея ⚠️ · структура данных ⚠️ · сложность ⚠️ · граничные случаи ⚠️

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

**Разбор задачи:** [`../../algo-solutions/02-extra/03-heap-hash/24-top-k-frequent-words.md`](../../algo-solutions/02-extra/03-heap-hash/24-top-k-frequent-words.md)