Encuentre el K-ésimo elemento más pequeño en dos matrices ordenadas en Java

1. Introducción

En este artículo, veremos cómo encontrar el k -ésimo elemento más pequeño en la unión de dos matrices ordenadas.

Primero, definiremos el problema exacto. En segundo lugar, veremos dos soluciones ineficientes pero sencillas. En tercer lugar, veremos una solución eficiente basada en una búsqueda binaria en las dos matrices. Finalmente, veremos algunas pruebas para verificar que nuestro algoritmo funciona.

También veremos fragmentos de código Java para todas las partes del algoritmo. Para simplificar, nuestra implementación solo operará con números enteros . Sin embargo, el algoritmo descrito funciona con todos los tipos de datos que son comparables e incluso podrían implementarse usando Genéricos.

2. ¿Cuál es el K- ésimo elemento más pequeño en la unión de dos matrices ordenadas?

2.1. El K- ésimo elemento más pequeño

Para encontrar el k -ésimo elemento más pequeño, también llamado estadístico de k -ésimo orden, en una matriz, normalmente usamos un algoritmo de selección. Sin embargo, estos algoritmos operan en una única matriz no ordenada, mientras que en este artículo queremos encontrar el k- ésimo elemento más pequeño en dos matrices ordenadas.

Antes de ver varias soluciones al problema, definamos exactamente lo que queremos lograr. Para eso, pasemos directamente a un ejemplo.

Se nos ha dado dos matrices (ordenados una y b ), que no necesariamente tienen que tener un número igual de elementos:

En estas dos matrices, queremos encontrar el k- ésimo elemento más pequeño. Más específicamente, queremos encontrar el k- ésimo elemento más pequeño en la matriz combinada y ordenada:

La matriz combinada y ordenada de nuestro ejemplo se muestra en (c). El primer elemento más pequeño es 3 y el cuarto elemento más pequeño es 20 .

2.2. Valores duplicados

También necesitaremos definir cómo manejar valores duplicados. Un elemento podría aparecer más de una vez en una de las matrices (elemento 3 en la matriz a ) y también volver a aparecer en la segunda matriz ( b ).

Si contamos los duplicados solo una vez, contaremos como se muestra en (c). Si contamos todas las apariciones de un elemento, contaremos como se muestra en (d).

En la parte restante de este artículo, contaremos los duplicados como se muestra en (d), contando así como si fueran elementos distintos.

3. Dos enfoques simples pero menos eficientes

3.1. Unir y luego ordenar las dos matrices

La forma más sencilla de encontrar el k- ésimo elemento más pequeño es unir las matrices, ordenarlas y devolver el k- ésimo elemento de la matriz resultante:

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]; }

Siendo n la longitud de la primera matriz y m la longitud de la segunda matriz, obtenemos la longitud combinada c = n + m .

Dado que la complejidad de la clasificación es O (c log c) , la complejidad general de este enfoque es O (n log n) .

Una desventaja de este enfoque es que necesitamos crear una copia de la matriz, lo que resulta en más espacio necesario.

3.2. Fusionar las dos matrices

Al igual que en un solo paso del algoritmo de clasificación Merge Sort, podemos fusionar las dos matrices y luego recuperar directamente el k- ésimo elemento.

La idea básica del algoritmo de fusión es comenzar con dos punteros, que apuntan a los primeros elementos de la primera y segunda matriz (a).

Luego comparamos los dos elementos ( 3 y 4 ) en los punteros, sumamos el más pequeño ( 3 ) al resultado y movemos ese puntero una posición hacia adelante (b). Nuevamente, comparamos los elementos en los punteros y agregamos el más pequeño ( 4 ) al resultado.

Continuamos de la misma manera hasta que todos los elementos se agregan al arreglo resultante. Si una de las matrices de entrada no tiene más elementos, simplemente copiamos todos los elementos restantes de la otra matriz de entrada a la matriz de resultados.

Podemos mejorar el rendimiento si no copiamos las matrices completas, pero nos detenemos cuando la matriz resultante tiene k elementos. Ni siquiera necesitamos crear una matriz adicional para la matriz combinada, pero solo podemos operar en las matrices originales.

Aquí hay una implementación en 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]; } }

Es sencillo entender que la complejidad temporal de este algoritmo es O ( k ). Una ventaja de este algoritmo es que se puede adaptar fácilmente para considerar elementos duplicados solo una vez .

4. Una búsqueda binaria en ambas matrices

¿Podemos hacerlo mejor que O ( k )? La respuesta es que podemos. La idea básica es hacer un algoritmo de búsqueda binaria sobre las dos matrices .

Para que esto funcione, necesitamos una estructura de datos que proporcione acceso de lectura en tiempo constante a todos sus elementos. En Java, podría ser una matriz o una ArrayList .

Definamos el esqueleto del método que vamos a implementar:

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

Here, we pass k and the two arrays as arguments. First, we'll validate the input; second, we handle some special cases and then do the binary search. In the next three sections, we'll look at these three steps in reverse order, so first, we'll see the binary search, second, the special cases, and finally, the parameter validation.

4.1. The Binary Search

The standard binary search, where we are looking for a specific element, has two possible outcomes: either we find the element we're looking for and the search is successful, or we don't find it and the search is unsuccessful. This is different in our case, where we want to find the kth smallest element. Here, we always have a result.

Let's look at how to implement that.

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).

El último algoritmo que vimos es un buen ejercicio teórico; sin embargo, para la mayoría de los propósitos prácticos, deberíamos considerar el uso de uno de los dos primeros algoritmos, que son mucho más simples que la búsqueda binaria en dos arreglos. Por supuesto, si el rendimiento es un problema, una búsqueda binaria podría ser una solución.

Todo el código de este artículo está disponible en GitHub.