Trova il K-esimo elemento più piccolo in due array ordinati in Java

1. Introduzione

In questo articolo vedremo come trovare l' elemento k -esimo più piccolo nell'unione di due array ordinati.

Innanzitutto, definiremo il problema esatto. In secondo luogo, vedremo due soluzioni inefficienti ma semplici. Terzo, esamineremo una soluzione efficiente basata su una ricerca binaria sui due array. Infine, esamineremo alcuni test per verificare che il nostro algoritmo funzioni.

Vedremo anche frammenti di codice Java per tutte le parti dell'algoritmo. Per semplicità, la nostra implementazione funzionerà solo su numeri interi . Tuttavia, l'algoritmo descritto funziona con tutti i tipi di dati che sono comparabili e potrebbero anche essere implementati utilizzando Generics.

2. Qual è il K- esimo elemento più piccolo nell'unione di due array ordinati?

2.1. Il K- esimo elemento più piccolo

Per trovare l' elemento k -esimo più piccolo, chiamato anche statistica dell'ordine k -esimo, in un array, usiamo tipicamente un algoritmo di selezione. Tuttavia, questi algoritmi operano su un singolo array non ordinato , mentre in questo articolo vogliamo trovare l' elemento k- esimo più piccolo in due array ordinati.

Prima di vedere diverse soluzioni al problema, definiamo esattamente cosa vogliamo ottenere. Per questo, passiamo direttamente a un esempio.

Ci viene dato due array (ordinato una e B ), che non devono necessariamente avere un numero uguale di elementi:

In questi due array, vogliamo trovare il k- esimo elemento più piccolo. Più specificamente, vogliamo trovare il k- esimo elemento più piccolo nell'array combinato e ordinato:

L'array combinato e ordinato per il nostro esempio è mostrato in (c). Il primo elemento più piccolo è 3 e il quarto elemento più piccolo è 20 .

2.2. Valori duplicati

Dovremo anche definire come gestire i valori duplicati. Un elemento potrebbe verificarsi più di una volta in uno degli array (elemento 3 nell'array a ) e anche nel secondo array ( b ).

Se contiamo i duplicati solo una volta, contiamo come mostrato in (c). Se contiamo tutte le occorrenze di un elemento, contiamo come mostrato in (d).

Nella parte restante di questo articolo, conteremo i duplicati come mostrato in (d), contandoli così come se fossero elementi distinti.

3. Due approcci semplici ma meno efficienti

3.1. Unisci e poi ordina i due array

Il modo più semplice per trovare il k- esimo elemento più piccolo è unire gli array, ordinarli e restituire il k- esimo elemento dell'array risultante:

int getKthElementSorted(int[] list1, int[] list2, int k) { int length1 = list1.length, length2 = list2.length; int[] combinedArray = new int[length1 + length2]; System.arraycopy(list1, 0, combinedArray, 0, list1.length); System.arraycopy(list2, 0, combinedArray, list1.length, list2.length); Arrays.sort(combinedArray); return combinedArray[k-1]; }

Con n è la lunghezza della prima matrice e m la lunghezza della seconda matrice, otteniamo la lunghezza combinata c = n + m .

Poiché la complessità per l'ordinamento è O (c log c) , la complessità complessiva di questo approccio è O (n log n) .

Uno svantaggio di questo approccio è che dobbiamo creare una copia dell'array, che si traduce in più spazio necessario.

3.2. Unisci i due array

Simile a un singolo passaggio dell'algoritmo di ordinamento Merge Sort, possiamo unire i due array e quindi recuperare direttamente l' elemento k- esimo.

L'idea di base dell'algoritmo di unione è iniziare con due puntatori, che puntano ai primi elementi del primo e del secondo array (a).

Quindi confrontiamo i due elementi ( 3 e 4 ) in corrispondenza dei puntatori, aggiungiamo quello più piccolo ( 3 ) al risultato e spostiamo quel puntatore di una posizione in avanti (b). Ancora una volta, confrontiamo gli elementi in corrispondenza dei puntatori e aggiungiamo quello più piccolo ( 4 ) al risultato.

Continuiamo allo stesso modo finché tutti gli elementi non vengono aggiunti all'array risultante. Se uno degli array di input non ha più elementi, copiamo semplicemente tutti gli elementi rimanenti dell'altro array di input nell'array dei risultati.

Possiamo migliorare le prestazioni se non copiamo gli array completi, ma ci fermiamo quando l'array risultante ha k elementi. Non abbiamo nemmeno bisogno di creare un array aggiuntivo per l'array combinato, ma possiamo operare solo sugli array originali.

Ecco un'implementazione in Java:

public static int getKthElementMerge(int[] list1, int[] list2, int k) { int i1 = 0, i2 = 0; while(i1 < list1.length && i2 < list2.length && (i1 + i2) < k) { if(list1[i1] < list2[i2]) { i1++; } else { i2++; } } if((i1 + i2) < k) { return i1  0 && i2 > 0) { return Math.max(list1[i1-1], list2[i2-1]); } else { return i1 == 0 ? list2[i2-1] : list1[i1-1]; } }

È semplice capire che la complessità temporale di questo algoritmo è O ( k ). Un vantaggio di questo algoritmo è che può essere facilmente adattato per considerare elementi duplicati solo una volta .

4. Una ricerca binaria su entrambi gli array

Possiamo fare meglio di O ( k )? La risposta è che possiamo. L'idea di base è fare un algoritmo di ricerca binaria sui due array .

Perché funzioni, abbiamo bisogno di una struttura dati che fornisca accesso in lettura a tempo costante a tutti i suoi elementi. In Java, potrebbe essere un array o un ArrayList .

Definiamo lo scheletro per il metodo che stiamo per implementare:

int findKthElement(int k, int[] list1, int[] list2) throws NoSuchElementException, IllegalArgumentException { // check input (see below) // handle special cases (see below) // binary search (see below) }

Qui passiamo k e i due array come argomenti. Innanzitutto, convalideremo l'input; secondo, gestiamo alcuni casi speciali e poi facciamo la ricerca binaria. Nelle prossime tre sezioni, esamineremo questi tre passaggi in ordine inverso, quindi per prima cosa vedremo la ricerca binaria, la seconda, i casi speciali e, infine, la convalida dei parametri.

4.1. La ricerca binaria

La ricerca binaria standard, in cui stiamo cercando un elemento specifico, ha due possibili risultati: o troviamo l'elemento che stiamo cercando e la ricerca ha esito positivo, oppure non lo troviamo e la ricerca non ha successo. Questo è diverso nel nostro caso, dove vogliamo trovare il k- esimo elemento più piccolo. Qui abbiamo sempre un risultato.

Diamo un'occhiata a come implementarlo.

4.1.1. Finding the Correct Number of Elements From Both Arrays

We start our search with a certain number of elements from the first array. Let's call that number nElementsList1. As we need k elements in total, the number nElementsList1 is:

int nElementsList2 = k - nElementsList1; 

As an example, let's say k = 8. We start with four elements from the first array and four elements from the second array (a).

If the 4th element in the first array is bigger than the 4th element in the second array, we know that we took too many elements from the first array and can decrease nElementsList1 (b). Otherwise, we know that we took too few elements and can increase nElementsList1 (b').

We continue until we have reached the stopping criteria. Before we look at what that is, let's look at the code for what we've described so far:

int right = k; int left = = 0; do { nElementsList1 = ((left + right) / 2) + 1; nElementsList2 = k - nElementsList1; if(nElementsList2 > 0) { if (list1[nElementsList1 - 1] > list2[nElementsList2 - 1]) { right = nElementsList1 - 2; } else { left = nElementsList1; } } } while(!kthSmallesElementFound(list1, list2, nElementsList1, nElementsList2));

4.1.2. Stopping Criteria

We can stop in two cases. First, we can stop if the maximum element we take from the first array is equal to the maximum element we take from the second (c). In this case, we can simply return that element.

Second, we can stop if the following two conditions are met (d):

  • The largest element to take from the first array is smaller than the smallest element we do not take from the second array (11 < 100).
  • The largest element to take from the second array is smaller than the smallest element we do not take from the first array (21 < 27).

It's easy to visualize (d') why that condition works: all elements we take from the two arrays are surely smaller than any other element in the two arrays.

Here's the code for the stopping criteria:

private static boolean foundCorrectNumberOfElementsInBothLists(int[] list1, int[] list2, int nElementsList1, int nElementsList2) { // we do not take any element from the second list if(nElementsList2 < 1) { return true; } if(list1[nElementsList1-1] == list2[nElementsList2-1]) { return true; } if(nElementsList1 == list1.length) { return list1[nElementsList1-1] <= list2[nElementsList2]; } if(nElementsList2 == list2.length) { return list2[nElementsList2-1] <= list1[nElementsList1]; } return list1[nElementsList1-1] <= list2[nElementsList2] && list2[nElementsList2-1] <= list1[nElementsList1]; }

4.1.3. The Return Value

Finally, we need to return the correct value. Here, we have three possible cases:

  • We take no elements from the second array, thus the target value is in the first array (e)
  • The target value is in the first array (e')
  • The target value is in the second array (e”)

Let's see this in code:

return nElementsList2 == 0 ? list1[nElementsList1-1] : max(list1[nElementsList1-1], list2[nElementsList2-1]);

Note that we do not need to handle the case where we don't take any element from the first array — we'll exclude that case in the handling of special cases later.

4.2. Initial Values for the Left and Right Borders

Until now, we initialized the right and left border for the first array with k and 0:

int right = k; int left = 0;

However, depending on the value of k, we need to adapt these borders.

First, if k exceeds the length of the first array, we need to take the last element as the right border. The reason for this is quite straightforward, as we cannot take more elements from the array than there are.

Second, if k is bigger than the number of elements in the second array, we know for sure that we need to take at least (k – length(list2)) from the first array. As an example, let's say k = 7. As the second array only has four elements, we know that we need to take at least 3 elements from the first array, so we can set L to 2:

Here's the code for the adapted left and right borders:

// correct left boundary if k is bigger than the size of list2 int left = k < list2.length ? 0 : k - list2.length - 1; // the inital right boundary cannot exceed the list1 int right = min(k-1, list1.length - 1);

4.3. Handling of Special Cases

Before we do the actual binary search, we can handle a few special cases to make the algorithm slightly less complicated and avoid exceptions. Here's the code with explanations in the comments:

// we are looking for the minimum value if(k == 1) { return min(list1[0], list2[0]); } // we are looking for the maximum value if(list1.length + list2.length == k) { return max(list1[list1.length-1], list2[list2.length-1]); } // swap lists if needed to make sure we take at least one element from list1 if(k <= list2.length && list2[k-1] < list1[0]) { int[] list1_ = list1; list1 = list2; list2 = list1_; }

4.4. Input Validation

Let's look at the input validation first. To prevent the algorithm from failing and throwing, for example, a NullPointerException or ArrayIndexOutOfBoundsException, we want to make sure that the three parameters meet the following conditions:

  • Both arrays must not be null and have at least one element
  • k must be >= 0 and cannot be bigger than the length of the two arrays together

Here's our validation in code:

void checkInput(int k, int[] list1, int[] list2) throws NoSuchElementException, IllegalArgumentException { if(list1 == null || list2 == null || k  list1.length + list2.length) { throw new NoSuchElementException(); } }

4.5. Full Code

Here's the full code of the algorithm we've just described:

public static int findKthElement(int k, int[] list1, int[] list2) throws NoSuchElementException, IllegalArgumentException { checkInput(k, list1, list2); // we are looking for the minimum value if(k == 1) { return min(list1[0], list2[0]); } // we are looking for the maximum value if(list1.length + list2.length == k) { return max(list1[list1.length-1], list2[list2.length-1]); } // swap lists if needed to make sure we take at least one element from list1 if(k <= list2.length && list2[k-1] < list1[0]) { int[] list1_ = list1; list1 = list2; list2 = list1_; } // correct left boundary if k is bigger than the size of list2 int left = k  0) { if (list1[nElementsList1 - 1] > list2[nElementsList2 - 1]) { right = nElementsList1 - 2; } else { left = nElementsList1; } } } while(!kthSmallesElementFound(list1, list2, nElementsList1, nElementsList2)); return nElementsList2 == 0 ? list1[nElementsList1-1] : max(list1[nElementsList1-1], list2[nElementsList2-1]); } private static boolean foundCorrectNumberOfElementsInBothLists(int[] list1, int[] list2, int nElementsList1, int nElementsList2) { // we do not take any element from the second list if(nElementsList2 < 1) { return true; } if(list1[nElementsList1-1] == list2[nElementsList2-1]) { return true; } if(nElementsList1 == list1.length) { return list1[nElementsList1-1] <= list2[nElementsList2]; } if(nElementsList2 == list2.length) { return list2[nElementsList2-1] <= list1[nElementsList1]; } return list1[nElementsList1-1] <= list2[nElementsList2] && list2[nElementsList2-1] <= list1[nElementsList1]; }

5. Testing the Algorithm

In our GitHub repository, there are many test cases that cover a lot of possible input arrays and also many corner cases.

Here, we only point out one of the tests, which tests not against static input arrays but compares the result of our double binary search algorithm to the result of the simple join-and-sort algorithm. The input consists of two randomized arrays:

int[] sortedRandomIntArrayOfLength(int length) { int[] intArray = new Random().ints(length).toArray(); Arrays.sort(intArray); return intArray; }

The following method performs one single test:

private void random() { Random random = new Random(); int length1 = (Math.abs(random.nextInt())) % 1000 + 1; int length2 = (Math.abs(random.nextInt())) % 1000 + 1; int[] list1 = sortedRandomIntArrayOfLength(length1); int[] list2 = sortedRandomIntArrayOfLength(length2); int k = (Math.abs(random.nextInt()) + 1) % (length1 + length2); int result = findKthElement(k, list1, list2); int result2 = getKthElementSorted(list1, list2, k); int result3 = getKthElementMerge(list1, list2, k); assertEquals(result2, result); assertEquals(result2, result3); }

And we can call the above method to run a large number of tests like that:

@Test void randomTests() { IntStream.range(1, 100000).forEach(i -> random()); }

6. Conclusion

In this article, we saw several ways of how to find the kth smallest element in the union of two sorted arrays. First, we saw a simple and straightforward O(n log n) algorithm, then a version with complexity O(n), and last, an algorithm that runs in O(log n).

L'ultimo algoritmo che abbiamo visto è un bell'esercizio teorico; tuttavia, per gli scopi più pratici, dovremmo considerare l'utilizzo di uno dei primi due algoritmi, che sono molto più semplici della ricerca binaria su due array. Ovviamente, se le prestazioni sono un problema, una ricerca binaria potrebbe essere una soluzione.

Tutto il codice in questo articolo è disponibile su GitHub.