Coding Interview Prep · Lekcja

N-ta najwyższa wartość za pomocą DENSE_RANK

Uogólnianie rozwiązania do n-tej różnej wartości i obsługa duplikatów

N-ta najwyższa wartość za pomocą DENSE_RANK to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Uogólnienie na N-te najwyższe wynagrodzenie

Gdy potrafią już Państwo znaleźć drugie najwyższe wynagrodzenie, rekruterzy od razu dopytują: „A teraz proszę podać N-te najwyższe”. Najczystsze i najłatwiejsze do uzasadnienia rozwiązanie wykorzystuje DENSE_RANK.

Schemat jest zawsze taki sam: uszeregować różne wynagrodzenia malejąco, a następnie odfiltrować wiersz, którego ranga jest równa N. Ponieważ logika nie zmienia się wraz z N, jedno rozwiązanie odpowiada na całą rodzinę podobnych pytań.

Zbudujemy to rozwiązanie krok po kroku, obsłużymy remisy i duplikaty oraz wyjaśnimy, dlaczego DENSE_RANK jest właściwą funkcją rankingową dla znaczenia „różna wartość”.

Podstawowy szablon

Oto uniwersalny szablon dla N-tego najwyższego wynagrodzenia. Stałą należy zastąpić wartością N wskazaną przez rekrutera.

Funkcję DENSE_RANK oblicza się w zapytaniu wewnętrznym — funkcja okna nie może znajdować się w WHERE — a następnie na zewnątrz filtruje się wartość rnk = N. Aby znaleźć trzecie najwyższe wynagrodzenie, należy ustawić filtr na 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;

Jak DENSE_RANK numeruje różne wartości

DENSE_RANK nadaje równym wartościom tę samą rangę i nigdy nie pozostawia po nich przerwy. To dokładnie odpowiada definicji „N-tej różnej wartości”, o którą chodzi rekruterom.

Dla wynagrodzeń 800, 800, 600, 600, 400:

800 -> ranga 1
600 -> ranga 2
400 -> ranga 3

Trzecie najwyższe wynagrodzenie to więc 400, mimo że istnieje pięć wierszy. Duplikaty są automatycznie łączone w jedną rangę.

Dlaczego RANK daje błędną odpowiedź

Po zastąpieniu go funkcją RANK wynik jest błędny. RANK pozostawia przerwy zależne od liczby remisujących wartości.

Dla wynagrodzeń 800, 800, 600, 600, 400:

800, 800 -> ranga 1 (dwa wiersze)
600, 600 -> ranga 3 (przerwa, brak rangi 2)
400 -> ranga 5

Filtrowanie za pomocą rnk = 3 zwraca 600, a rnk = 2 nie zwraca niczego. Jeśli rekruter nie oczekuje konkretnie rankingu stosowanego w zawodach, DENSE_RANK jest właściwym wyborem dla „N-tego różnego wynagrodzenia”.

Dlaczego ROW_NUMBER również jest tu błędne

ROW_NUMBER nadaje każdemu wierszowi unikalny numer, całkowicie ignorując remisy. Dla wynagrodzeń 800, 800, 600, 600, 400 zwróci wartości 1, 2, 3, 4, 5.

Dlatego rn = 3 zwróci 600, ale rn = 2 zwróci duplikat 800, a nie drugą różną wartość. ROW_NUMBER odpowiada na pytanie o „N-ty wiersz”, a nie o „N-tą różną wartość”.

ROW_NUMBER należy stosować tylko wtedy, gdy pytanie rzeczywiście dotyczy konkretnego wiersza, na przykład przy deduplikacji lub wybieraniu top N wierszy z każdej grupy z zachowaniem dokładnie jednego wiersza.

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

Bezpieczne parametryzowanie N

W rzeczywistym kodzie nie należy wpisywać rangi na stałe. Należy przekazać N jako parametr i porównywać z nim wynik. Definicja okna pozostaje identyczna; parametryzowany jest tylko filtr zewnętrzny.

W ten sposób można również zwrócić wszystkie wynagrodzenia remisujące na randze N: ponieważ DENSE_RANK nadaje tę samą rangę wartościom remisującym, WHERE rnk = N może zwrócić wiele wierszy, jeśli kilku pracowników ma N-te różne wynagrodzenie. Często właśnie takie zachowanie jest pożądane.

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

Uogólnienie skorelowanego zliczania

Podejście sprzed funkcji okna również można uogólnić: wynagrodzenie jest N-tym najwyższym różnym wynagrodzeniem, gdy istnieje dokładnie N - 1 różnych wynagrodzeń ściśle od niego wyższych.

W przypadku trzeciego najwyższego wynagrodzenia należy wymagać dokładnie dwóch różnych wyższych wynagrodzeń. Działa to w starszych silnikach baz danych bez funkcji okna, ale słabo się skaluje, ponieważ wewnętrzne zliczanie jest ponownie wykonywane dla każdego wiersza zapytania zewnętrznego.

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

Postać funkcji MySQL, o którą pytają rekruterzy

Zadanie w stylu LeetCode dotyczące „N-tego najwyższego wynagrodzenia” często wymaga funkcji składowanej zwracającej pojedynczą wartość. Jej treść to po prostu szablon z DENSE_RANK opakowany tak, aby zwracał jedno wynagrodzenie.

Podczas rozmowy kwalifikacyjnej nie trzeba zapamiętywać dokładnej składni funkcji, ale warto znać zwięzły idiom MySQL, w którym LIMIT N-1, 1 jest stosowane do różnych wynagrodzeń.

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

Przykład: czwarte najwyższe wynagrodzenie

Wynagrodzenia: 1000, 900, 900, 700, 500, 500, 300.

Różne wynagrodzenia w kolejności malejącej z użyciem DENSE_RANK:

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

Czwarte najwyższe wynagrodzenie to 500. Należy zauważyć, że oba wiersze z wartością 500 mają rangę 4, więc filtrowanie za pomocą rnk = 4 zwróci obu pracowników zarabiających 500, jeśli zostaną wybrane również ich identyfikatory.

Uwagi dotyczące wydajności

Jak te podejścia wypadają przy dużej skali?

DENSE_RANK: jedno sortowanie danych, a następnie filtrowanie. Rozwiązanie jest wydajne, a optymalizator może użyć indeksu na kolumnie salary do sortowania.
Skorelowane zliczanie: potencjalnie O(n²), ponieważ agregat wewnętrzny wykonuje się dla każdego wiersza. Należy unikać tego rozwiązania w przypadku dużych tabel.
LIMIT/OFFSET: szybkie dla małych wartości N, ale nadal wymaga sortowania, a duże wartości OFFSET powodują skanowanie i odrzucanie wielu wierszy.

Rozpoczęcie od DENSE_RANK prawie zawsze jest dobrym wyborem.

Przypadki brzegowe, o których warto wspomnieć

Doświadczeni kandydaci wskazują przypadki brzegowe, zanim zostaną o nie zapytani:

N większe niż liczba różnych wynagrodzeń: filtr nie dopasuje żadnych wierszy i zwróci pusty wynik. W lekcji 4 pokażemy, jak wymusić zwrócenie pojedynczej wartości NULL.
Remisy na randze N: DENSE_RANK zwróci każdego remisującego pracownika; należy ustalić, czy takie zachowanie jest pożądane.
N = 1: szablon nadal działa i zwraca maksimum.

Szybki test

Zastosuj szablon dla N-tego najwyższego wynagrodzenia.

Podsumowanie

W przypadku N-tego najwyższego wynagrodzenia istnieje jedno podstawowe rozwiązanie: uszeregować różne wynagrodzenia za pomocą DENSE_RANK() OVER (ORDER BY salary DESC) w podzapytaniu, a następnie zastosować filtr WHERE rnk = N.

DENSE_RANK oznacza „N-tą różną wartość”: wartości remisujące mają tę samą rangę i nie występują przerwy.
RANK wprowadza przerwy, a ROW_NUMBER zlicza wiersze, nie wartości.
Trik ze skorelowanym zliczaniem = N-1 uogólnia tę samą ideę bez użycia funkcji okna, ale słabo się skaluje.

Zawsze należy wspomnieć o przypadku, w którym „N przekracza liczbę dostępnych wartości”; rozwiążemy go w następnej części.

Często zadawane pytania

Czy lekcja „N-ta najwyższa wartość za pomocą DENSE_RANK” jest bezpłatna?

Tak — pełny tekst „N-ta najwyższa wartość za pomocą DENSE_RANK” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „N-ta najwyższa wartość za pomocą DENSE_RANK”?

Uogólnianie rozwiązania do n-tej różnej wartości i obsługa duplikatów Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.

Ile czasu zajmuje lekcja „N-ta najwyższa wartość za pomocą DENSE_RANK”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

Druga najwyższa pensja na pięć sposobów
N-ta najwyższa wartość za pomocą DENSE_RANK
Najlepiej zarabiająca osoba w dziale
Zwracanie NULL, gdy nie istnieje n-ta wartość

← Powrót do Coding Interview Prep