Trovare i primi elementi K in un array Java

1. Panoramica

In questo tutorial, implementeremo diverse soluzioni al problema di trovare i k elementi più grandi in un array con Java. Per descrivere la complessità del tempo useremo la notazione Big-O.

2. Soluzione per la forza bruta

La soluzione a forza bruta a questo problema è scorrere l'array dato k volte . In ogni iterazione, troveremo il valore più grande . Quindi rimuoveremo questo valore dall'array e lo inseriremo nell'elenco di output:

public List findTopK(List input, int k) { List array = new ArrayList(input); List topKList = new ArrayList(); for (int i = 0; i < k; i++) { int maxIndex = 0; for (int j = 1; j  array.get(maxIndex)) { maxIndex = j; } } topKList.add(array.remove(maxIndex)); } return topKList; }

Se supponiamo che n sia la dimensione dell'array dato, la complessità temporale di questa soluzione è O (n * k) . Inoltre, questa è la soluzione più inefficiente.

3. Approccio alle collezioni Java

Tuttavia, esistono soluzioni più efficienti a questo problema. In questa sezione, ne spiegheremo due utilizzando le raccolte Java.

3.1. TreeSet

TreeSet ha una struttura dati albero rosso-nero come spina dorsale. Di conseguenza, assegnare un valore a questo set costa O (log n) . TreeSet è una raccolta ordinata. Pertanto, possiamo mettere tutti i valori nel TreeSet ed estrarne il primo k :

public List findTopK(List input, int k) { Set sortedSet = new TreeSet(Comparator.reverseOrder()); sortedSet.addAll(input); return sortedSet.stream().limit(k).collect(Collectors.toList()); }

La complessità temporale di questa soluzione è O (n * log n) . Soprattutto, questo dovrebbe essere più efficiente dell'approccio a forza bruta se k ≥ log n .

È importante ricordare che TreeSet non contiene duplicati. Di conseguenza, la soluzione funziona solo per una matrice di input con valori distinti.

3.2. PriorityQueue

PriorityQueue è una struttura dati Heap in Java. Con il suo aiuto, siamo in grado di ottenere un (n * log k) O soluzione . Inoltre, questa sarà una soluzione più veloce della precedente. A causa del problema dichiarato, k è sempre inferiore alla dimensione dell'array. Quindi, significa che O (n * log k) ≤ O (n * log n).

L'algoritmo itera una volta attraverso l'array dato . Ad ogni iterazione, aggiungeremo un nuovo elemento all'heap. Inoltre, manterremo la dimensione dell'heap minore o uguale a k . Quindi, dovremo rimuovere elementi extra dall'heap e aggiungerne di nuovi. Di conseguenza, dopo l'iterazione nell'array, l'heap conterrà i k valori più grandi:

public List findTopK(List input, int k) { PriorityQueue maxHeap = new PriorityQueue(); input.forEach(number -> { maxHeap.add(number); if (maxHeap.size() > k) { maxHeap.poll(); } }); List topKList = new ArrayList(maxHeap); Collections.reverse(topKList); return topKList; }

4. Algoritmo di selezione

Esistono molti approcci per risolvere il problema dato. E, sebbene esuli dallo scopo di questo tutorial, l' utilizzo dell'approccio algoritmo di selezione sarà il migliore perché produce una complessità temporale lineare.

5. conclusione

In questo tutorial, abbiamo descritto diverse soluzioni per trovare i k elementi più grandi in un array.

Come al solito, il codice di esempio è disponibile su GitHub.