Coding Interview Prep · Урок

N-е по величине значение с DENSE_RANK

Обобщайте поиск до N-го уникального значения и обрабатывайте дубликаты.

«N-е по величине значение с DENSE_RANK» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Обобщение для N-го по величине значения

Когда вы умеете находить вторую по величине зарплату, интервьюеры сразу переходят к следующему вопросу: «А теперь найдите N-ю по величине». Самый понятный и убедительный ответ использует DENSE_RANK.

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

Мы постепенно построим решение, учтём равные значения и дубликаты и обсудим, почему DENSE_RANK — правильная функция ранжирования для семантики «различного значения».

Основной шаблон

Вот универсальный шаблон для поиска N-й по величине зарплаты. Замените константу нужным значением N, которое назовёт интервьюер.

Вы вычисляете DENSE_RANK во внутреннем запросе (оконная функция не может находиться в WHERE), а затем снаружи фильтруете по условию rnk = N. Для третьей по величине зарплаты установите фильтр rnk = 3.

SELECT salary AS nth_highest
FROM (
  SELECT salary,
         DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
  FROM employee
) ranked
WHERE rnk = 3;

Как DENSE_RANK нумерует различные значения

DENSE_RANK присваивает одинаковым значениям один и тот же ранг и никогда не оставляет после них пропусков. Это в точности определение «N-го различного значения», которое имеют в виду интервьюеры.

Для зарплат 800, 800, 600, 600, 400:

800 -> ранг 1
600 -> ранг 2
400 -> ранг 3

Таким образом, третья по величине зарплата — 400, хотя всего строк пять. Дубликаты автоматически объединяются в один ранг.

Почему RANK даёт неправильный ответ

Замените его на RANK — и ответ станет неверным. RANK оставляет пропуски, соответствующие количеству одинаковых значений.

Для зарплат 800, 800, 600, 600, 400:

800, 800 -> ранг 1 (два значения)
600, 600 -> ранг 3 (пропуск, ранга 2 нет)
400 -> ранг 5

Фильтр по условию rnk = 3 возвращает 600, а rnk = 2 не возвращает ничего. Если интервьюер специально не просит использовать соревновательную схему ранжирования, для «N-й различной зарплаты» правильна DENSE_RANK.

Почему ROW_NUMBER здесь тоже не подходит

ROW_NUMBER присваивает уникальный номер каждой строке, полностью игнорируя равные значения. Для зарплат 800, 800, 600, 600, 400 получаются номера 1, 2, 3, 4, 5.

Поэтому rn = 3 возвращает 600, а rn = 2 возвращает дубликат 800, а не второе различное значение. ROW_NUMBER отвечает на вопрос «какая строка является N-й», а не «какое значение является N-м различным».

Используйте ROW_NUMBER только тогда, когда вопрос действительно требует найти конкретную строку, например при удалении дубликатов или при выборе ровно одной из N лучших строк в каждой группе.

SELECT salary, ROW_NUMBER() OVER (ORDER BY salary DESC) AS rn
FROM employee;

Безопасная параметризация N

В настоящем коде не следует прописывать ранг напрямую. Передавайте N как параметр и сравнивайте с ним. Определение окна остаётся неизменным; параметризуется только внешний фильтр.

Здесь же можно вернуть все зарплаты с одинаковым значением на ранге N: поскольку DENSE_RANK присваивает одинаковым значениям один и тот же ранг, условие WHERE rnk = N может вернуть несколько строк, если несколько сотрудников получают одинаковую N-ю различную зарплату. Часто это именно нужное поведение.

SELECT id, salary
FROM (
  SELECT id, salary,
         DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
  FROM employee
) ranked
WHERE rnk = :n;

Обобщение с помощью подсчёта в коррелированном подзапросе

Подход без оконных функций тоже обобщается: зарплата является N-й по величине различной зарплатой, если строго выше неё находятся ровно N - 1 различных зарплат.

Для третьей по величине зарплаты требуется ровно 2 различные зарплаты выше неё. Этот способ работает в старых СУБД без оконных функций, но плохо масштабируется, поскольку внутренний подсчёт повторно выполняется для каждой внешней строки.

SELECT DISTINCT salary AS nth_highest
FROM employee e
WHERE (
  SELECT COUNT(DISTINCT e2.salary)
  FROM employee e2
  WHERE e2.salary > e.salary
) = 2;

Форма функции MySQL, которую часто требуют интервьюеры

В задачах в стиле LeetCode с формулировкой «N-я по величине зарплата» часто требуется хранимая функция, возвращающая одно значение. Её тело — это просто шаблон DENSE_RANK, обёрнутый так, чтобы вернуть одну зарплату.

Вам не нужно заучивать точный синтаксис функции для собеседования, но стоит знать, что LIMIT N-1, 1 для различных зарплат — это краткий идиоматичный синтаксис MySQL.

SELECT DISTINCT salary
FROM employee
ORDER BY salary DESC
LIMIT 1 OFFSET 2;  -- N = 3, so OFFSET N-1

Разобранный пример: 4-я по величине зарплата

Зарплаты: 1000, 900, 900, 700, 500, 500, 300.

Различные значения по убыванию с DENSE_RANK:

1000 -> 1
900 -> 2
700 -> 3
500 -> 4
300 -> 5

Четвёртая по величине зарплата — 500. Обратите внимание: обе строки с зарплатой 500 имеют ранг 4, поэтому фильтр rnk = 4 возвращает обоих сотрудников, получающих 500, если выбрать также их идентификаторы.

Замечания о производительности

Как эти подходы сравниваются при работе с большими объёмами данных?

DENSE_RANK: одна сортировка данных, затем фильтр. Эффективный подход, и планировщик может использовать индекс по зарплате для сортировки.
Коррелированный подсчёт: потенциально O(n в квадрате), поскольку внутренний агрегат выполняется для каждой строки. Избегайте этого подхода на больших таблицах.
LIMIT/OFFSET: быстро при малом N, но всё равно требует сортировки, а при больших смещениях приходится просматривать и отбрасывать много строк.

Начинайте с DENSE_RANK — и редко ошибётесь.

Пограничные случаи, о которых стоит упомянуть

Опытные кандидаты сами называют пограничные случаи, не дожидаясь вопроса:

N больше количества различных зарплат: фильтр не находит строк и возвращает пустой результат. На уроке 4 мы рассмотрим, как принудительно вернуть один NULL.
Равные значения на ранге N: DENSE_RANK возвращает всех сотрудников с одинаковой зарплатой; решите, нужно ли вам именно это.
N = 1: шаблон по-прежнему работает и возвращает максимум.

Быстрая проверка

Примените шаблон для N-й по величине зарплаты.

Итоги

Для поиска N-й по величине зарплаты есть один основной ответ: в подзапросе ранжируйте различные зарплаты с помощью DENSE_RANK() OVER (ORDER BY salary DESC), затем примените фильтр WHERE rnk = N.

DENSE_RANK означает «N-е различное значение»: одинаковые значения получают один ранг, а пропусков нет.
RANK создаёт пропуски, а ROW_NUMBER считает строки, а не значения.
Приём коррелированный подсчёт = N-1 обобщает ту же идею без оконных функций, но плохо масштабируется.

Всегда отмечайте пограничный случай «N превышает количество доступных значений» — далее мы его решим.

Часто задаваемые вопросы

Урок «N-е по величине значение с DENSE_RANK» бесплатный?

Да — полный текст урока «N-е по величине значение с DENSE_RANK» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «N-е по величине значение с DENSE_RANK»?

Обобщайте поиск до N-го уникального значения и обрабатывайте дубликаты. Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «N-е по величине значение с DENSE_RANK»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

Вторая по величине зарплата: пять способов
N-е по величине значение с DENSE_RANK
Самый высокооплачиваемый сотрудник отдела
Возврат NULL при отсутствии N-го значения

← Назад к Coding Interview Prep