Come contare nel tempo lineare peggiore?

Question

Questa domanda e questa domanda Mi ha fatto pensare un po '. Per ordinare una serie di lunghezza $ n $ insieme a $ k $ elementi unici in $ O (n + k log k) $, dobbiamo essere in grado di archiviare conteggi di valori nell'array. Ci sono alcuni suggerimenti, ma sto cercando un modo per farlo nel peggiore dei casi lineari. Più specificamente:

Dato un elenco $ A $ di $ n $ elementi con $ k $ elementi distinti, determina un elenco di tuple $ U = {(x_i, c_i) }^k $ di tutti gli elementi unici $ x_i in un $ tale che $ c_i $ è il conteggio dell'elemento $ x_i $ in $ A $.

Ecco alcune idee (fallite) che ho avuto e sono state suggerite:

1. Albero di ricerca binaria equilibrato - con questo ci vorrà $ O ( log k) $ inserire nell'albero e aumentare i valori. Dopo gli inserti potremmo fare un attraversamento dell'albero $ O (k) $. Quindi, il tempo totale viene fuori $ O (n log k) $ che è troppo lento.
2. Mappa hash - Con questo possiamo ottenere $ O (1) $ previsto inserire e quindi $ O (n) $ previsto volta. Tuttavia, questo non è ancora $ O (n) $ caso peggiore.
3. Mappatura dello spazio vuoto - Trova l'elemento minimo e massimo in $ A $. Allocare (ma fai non Inizializza) sufficiente memoria per coprire questo intervallo. Usa questa memoria fondamentalmente come una mappa hash e includi un hash casuale in modo da non provare ad accedere alla memoria corrotta. Questa strategia presenta problemi. (1) È probabilistico con probabilità molto molto bassa di fallimento, ma ancora non garantito. L'uso di memoria come questo ci limita a vincoli fluttuanti o interi.
4. Array associativi - Ci sono molti altri Arresi associative che possono essere utilizzate, simili alle mappe hash e ai BST, ma non trovo nulla che corrisponda a questi vincoli.

Forse c'è qualche metodo ovvio che mi manca, ma penso anche che potrebbe essere potenzialmente non essere possibile. Quali sono i tuoi pensieri?