L'ennesimo valore più alto con DENSE_RANK
Generalizzare alla N-esima valore distinto e gestire i duplicati
L'ennesimo valore più alto con DENSE_RANK è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Generalizzare all'N-esimo valore più alto
Una volta imparato a trovare il secondo stipendio più alto, i selezionatori incalzano subito: "Ora trovi l'N-esimo stipendio più alto." La risposta più chiara e difendibile utilizza DENSE_RANK.
Lo schema è sempre lo stesso: assegnare un rango agli stipendi distinti in ordine decrescente e poi filtrare la riga il cui rango è uguale a N. Poiché la logica non cambia al variare di N, questo unico approccio risponde a tutta la famiglia di domande.
Lo costruiremo passo dopo passo, gestiremo pari merito e duplicati e spiegheremo perché DENSE_RANK è la funzione di ranking corretta per la semantica dei "valori distinti".
Il modello di base
Ecco il modello riutilizzabile per l'N-esimo valore più alto. Sostituite la costante con il valore N richiesto dal selezionatore.
Calcolate DENSE_RANK in una query interna, perché la funzione finestra non può essere usata in WHERE, e poi filtrate all'esterno con rnk = N. Per il terzo stipendio più alto, impostate il filtro su 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;Come DENSE_RANK numera i valori distinti
DENSE_RANK assegna lo stesso rango ai valori uguali e non lascia mai una lacuna nei ranghi successivi. Questa è esattamente la definizione di "N-esimo valore distinto" a cui si riferiscono i selezionatori.
Per gli stipendi 800, 800, 600, 600, 400:
- 800 -> rango 1
- 600 -> rango 2
- 400 -> rango 3
Quindi il terzo stipendio più alto è 400, anche se le righe sono cinque. I duplicati vengono automaticamente ricondotti a un unico rango.
Perché RANK restituisce la risposta sbagliata
Sostituite RANK e la risposta non sarà più corretta. RANK lascia lacune proporzionali al numero di valori a pari merito.
Per gli stipendi 800, 800, 600, 600, 400:
- 800, 800 -> rango 1 (due occorrenze)
- 600, 600 -> rango 3 (lacuna, nessun rango 2)
- 400 -> rango 5
Filtrare per rnk = 3 restituisce 600, mentre rnk = 2 non restituisce nulla. A meno che il selezionatore non chieda esplicitamente un ranking in stile competizione, DENSE_RANK è corretto per "l'N-esimo stipendio distinto".
Perché anche ROW_NUMBER è sbagliato in questo caso
ROW_NUMBER assegna un numero univoco a ogni riga, ignorando completamente i pari merito. Per gli stipendi 800, 800, 600, 600, 400 produce 1, 2, 3, 4, 5.
Di conseguenza rn = 3 restituisce 600, mentre rn = 2 restituisce il duplicato di 800, non un secondo valore distinto. ROW_NUMBER risponde alla domanda "qual è l'N-esima riga?", non a "qual è l'N-esimo valore distinto?"
Usate ROW_NUMBER solo quando la domanda richiede davvero una riga specifica, ad esempio per eliminare duplicati o mantenere esattamente una riga per ciascun gruppo tra le prime N.
SELECT salary, ROW_NUMBER() OVER (ORDER BY salary DESC) AS rn
FROM employee;Parametrizzare N in modo sicuro
Nel codice reale non dovreste fissare il rango nel codice. Passate N come parametro e confrontatelo con il rango. La definizione della finestra resta identica; solo il filtro esterno viene parametrizzato.
È anche il modo per restituire tutti gli stipendi a pari merito al rango N: poiché DENSE_RANK assegna lo stesso rango ai valori pari, WHERE rnk = N può restituire più righe se diversi dipendenti condividono l'N-esimo stipendio distinto, comportamento spesso desiderato.
SELECT id, salary
FROM (
SELECT id, salary,
DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
FROM employee
) ranked
WHERE rnk = :n;La generalizzazione del conteggio correlato
Anche l'approccio precedente alle funzioni finestra si generalizza: uno stipendio è l'N-esimo stipendio distinto più alto quando esistono esattamente N - 1 stipendi distinti strettamente superiori.
Per il terzo stipendio più alto, richiedete esattamente 2 stipendi distinti più alti. Funziona nei motori meno recenti che non supportano le funzioni finestra, ma scala male perché il conteggio interno viene rieseguito per ogni riga esterna.
SELECT DISTINCT salary AS nth_highest
FROM employee e
WHERE (
SELECT COUNT(DISTINCT e2.salary)
FROM employee e2
WHERE e2.salary > e.salary
) = 2;La forma di funzione MySQL richiesta nei colloqui
Il problema in stile LeetCode dell'"N-esimo stipendio più alto" richiede spesso una funzione memorizzata che restituisca un singolo valore. Il corpo della funzione è semplicemente il modello con DENSE_RANK, adattato per restituire uno stipendio.
In un colloquio non è necessario memorizzare la sintassi esatta della funzione, ma è utile sapere che LIMIT N-1, 1 sugli stipendi distinti è la forma idiomatica compatta di MySQL.
SELECT DISTINCT salary
FROM employee
ORDER BY salary DESC
LIMIT 1 OFFSET 2; -- N = 3, so OFFSET N-1Esempio svolto: il quarto stipendio più alto
Stipendi: 1000, 900, 900, 700, 500, 500, 300.
Valori distinti in ordine decrescente con DENSE_RANK:
- 1000 -> 1
- 900 -> 2
- 700 -> 3
- 500 -> 4
- 300 -> 5
Il quarto stipendio più alto è 500. Notate che entrambe le righe con 500 condividono il rango 4, quindi il filtro rnk = 4 restituisce entrambi i dipendenti che guadagnano 500, se selezionate anche i loro id.
Note sulle prestazioni
Come si confrontano gli approcci su larga scala?
- DENSE_RANK: un ordinamento dei dati seguito da un filtro. È efficiente e il planner può utilizzare un indice su salary per l'ordinamento.
- Conteggio correlato: potenzialmente O(n al quadrato), perché l'aggregato interno viene eseguito per ogni riga. Evitatelo su tabelle di grandi dimensioni.
- LIMIT/OFFSET: è veloce per valori piccoli di N, ma deve comunque eseguire l'ordinamento; inoltre, offset grandi costringono a scorrere e scartare molte righe.
Se iniziate con DENSE_RANK, raramente sbaglierete.
Casi limite da menzionare
I candidati più preparati segnalano i casi limite prima che venga loro chiesto:
- N maggiore del numero di stipendi distinti: il filtro non corrisponde a nessuna riga e il risultato è vuoto. La lezione 4 spiega come forzare un singolo
NULL. - Pari merito al rango N: DENSE_RANK restituisce ogni dipendente a pari merito; decidete se è il comportamento desiderato.
- N = 1: il modello funziona comunque e restituisce il valore massimo.
Verifica rapida
Applicate il modello per l'N-esimo valore più alto.
Riepilogo
Per trovare l'N-esimo stipendio più alto esiste una risposta predefinita: assegnare un rango agli stipendi distinti con DENSE_RANK() OVER (ORDER BY salary DESC) in una sottoquery, quindi filtrare con WHERE rnk = N.
- DENSE_RANK significa "N-esimo valore distinto": i valori a pari merito condividono un rango e non ci sono lacune.
- RANK introduce lacune; ROW_NUMBER conta le righe, non i valori.
- Il trucco del conteggio correlato = N-1 generalizza la stessa idea senza funzioni finestra, ma scala male.
Segnalate sempre il caso limite in cui "N supera i valori disponibili": lo risolveremo nella prossima lezione.
Impara Coding Interview Prep con un tutor IA — gratis
Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.
- Corsi
- 90
- Lezioni
- 360
Domande Frequenti
La lezione «L'ennesimo valore più alto con DENSE_RANK» è gratuita?
Sì — il testo completo di «L'ennesimo valore più alto con DENSE_RANK» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «L'ennesimo valore più alto con DENSE_RANK»?
Generalizzare alla N-esima valore distinto e gestire i duplicati Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «L'ennesimo valore più alto con DENSE_RANK»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Il secondo stipendio più alto: cinque metodi
- L'ennesimo valore più alto con DENSE_RANK
- Il reddito più alto per reparto
- Restituire NULL quando non esiste l'ennesimo valore