Ordini con il quicksort (O(n log n)), quindi per individuare gli elementi duplicati ti basta scorrere l'array una sola volta, visto che nell'array ordinato tutti i duplicati dello stesso elemento sono consecutivi.