0Pricing
Coding Interview Prep · レッスン

DENSE_RANKでn番目に高い値を求める

n番目の異なる値を求める方法に一般化し、重複を扱います。

「DENSE_RANKでn番目に高い値を求める」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

N番目に高い値への一般化

2番目に高い給与を求められるようになると、面接官はすぐに「では、N番目に高い給与を求めてください」と続けます。最も簡潔で説明しやすい解答はDENSE_RANKを使う方法です。

パターンは常に同じです。異なる給与を降順にランク付けし、ランクがNに等しい行をフィルタリングします。Nが変わってもロジックは変わらないため、この1つの方法で一連の問題全体に答えられます。

ここでは、同率と重複を処理しながら実装し、「異なる値」という意味ではなぜDENSE_RANKが適切なランキング関数なのかを説明します。

基本テンプレート

これが再利用できるN番目に高い値を求めるテンプレートです。面接官から指定されたNに合わせて定数を置き換えてください。

内側のクエリでDENSE_RANKを計算します（ウィンドウ関数はWHEREには置けません）。その後、外側でrnk = Nに絞り込みます。3番目に高い給与を求める場合は、フィルターを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

したがって、行が5つあっても3番目に高い給与は400です。重複は自動的に1つのランクにまとめられます。

RANKでは誤った結果になる理由

RANKに置き換えると、結果は誤りになります。RANKは同率の数に応じて順位を飛ばします。

給与が800、800、600、600、400の場合:

  • 800、800 -> ランク1（2件）
  • 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は異なる2番目の値ではなく、重複している800を返します。ROW_NUMBERが答えるのは「N番目の値」ではなく「N番目の行」です。

ROW_NUMBERは、重複排除や、各グループから必ず1行だけ残すトップNなど、本当に特定の行が必要な場合にだけ使ってください。

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

Nを安全にパラメーター化する

実際のコードではランクをハードコードせず、Nをパラメーターとして渡して比較します。ウィンドウ定義は変わらず、外側のフィルターだけをパラメーター化します。

ここでは、ランクNで同率になったすべての給与を返すこともできます。DENSE_RANKは同率の値に同じランクを付けるため、N番目に異なる給与を複数の従業員が共有している場合、WHERE rnk = 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個ある場合です。

3番目に高い給与の場合は、それより高い異なる給与がちょうど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番目に高い給与」問題では、単一の値を返すストアド関数を求められることがよくあります。本体は、1つの給与を返すように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

4番目に高い給与は500です。500の2行はどちらもランク4になるため、rnk = 4で絞り込み、従業員のIDも選択すると、500を受け取っている両方の従業員が返されることに注意してください。

パフォーマンスに関する注意点

規模が大きくなった場合、各方法はどのように比較できるでしょうか。

  • DENSE_RANK: データ全体を1回ソートしてからフィルタリングします。効率的で、クエリプランナーはsalaryのインデックスを並べ替えに利用できます。
  • 相関カウント: 内側の集約が各行に対して実行されるため、O(nの2乗)になる可能性があります。大きなテーブルでは避けてください。
  • LIMIT/OFFSET: 小さなNに対しては高速ですが、それでもソートが必要です。また、大きなオフセットでは多くの行をスキャンして破棄することになります。

DENSE_RANKを基本解答にすれば、ほとんどの場合に適切な選択になります。

説明しておきたいエッジケース

優秀な候補者は、質問される前にエッジケースを指摘します。

  • Nが異なる給与の個数を超える場合: フィルターに一致する行がなく、空の結果が返ります。1つのNULLを強制的に返す方法はレッスン4で扱います。
  • ランクNで同率になる場合: DENSE_RANKは同率の従業員をすべて返します。それが必要かどうかを判断してください。
  • N = 1: このテンプレートはそのまま機能し、最大値を返します。

クイックチェック

N番目に高い値を求めるテンプレートを適用してみましょう。

まとめ

N番目に高い給与を求める基本解答は1つです。サブクエリ内でDENSE_RANK() OVER (ORDER BY salary DESC)を使って異なる給与をランク付けし、WHERE rnk = Nで絞り込みます。

  • DENSE_RANKは「N番目に異なる値」を意味し、同率には同じランクを付け、順位を飛ばしません。
  • RANKは順位を飛ばし、ROW_NUMBERは値ではなく行を数えます。
  • 相関カウント = N-1の方法は、同じ考え方をウィンドウ関数なしで実現しますが、スケーラビリティに欠けます。

「Nが利用可能な値の個数を超える」エッジケースは必ず指摘してください。次にこのケースを解決します。

よくある質問

「DENSE_RANKでn番目に高い値を求める」レッスンは無料ですか？

はい。「DENSE_RANKでn番目に高い値を求める」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「DENSE_RANKでn番目に高い値を求める」で何を学びますか？

n番目の異なる値を求める方法に一般化し、重複を扱います。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

「DENSE_RANKでn番目に高い値を求める」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 2番目に高い給与を求める5つの方法
  2. DENSE_RANKでn番目に高い値を求める
  3. 部署ごとの最高給与者
  4. n番目の値がない場合にNULLを返す
← Coding Interview Prepに戻る