Trouvez le Kth plus petit élément dans deux tableaux triés en Java

1. Introduction

Dans cet article, nous verrons comment trouver le k élément e le plus petit dans l'union de deux tableaux triés.

Tout d'abord, nous définirons le problème exact. Deuxièmement, nous verrons deux solutions inefficaces mais simples. Troisièmement, nous examinerons une solution efficace basée sur une recherche binaire sur les deux tableaux. Enfin, nous examinerons quelques tests pour vérifier que notre algorithme fonctionne.

Nous verrons également des extraits de code Java pour toutes les parties de l'algorithme. Par souci de simplicité, notre implémentation ne fonctionnera que sur des entiers . Cependant, l'algorithme décrit fonctionne avec tous les types de données qui sont comparables et pourraient même être implémentés à l'aide de Generics.

2. Quel est le K e plus petit élément de l'union de deux tableaux triés?

2.1. Le K e plus petit élément

Pour trouver le k e-plus petit élément, également appelé k statistique e ordre, dans un tableau, nous utilisons généralement un algorithme de sélection. Cependant, ces algorithmes fonctionnent sur un seul tableau non trié, alors que dans cet article, nous voulons trouver le k e plus petit élément dans deux tableaux triés.

Avant de voir plusieurs solutions au problème, définissons exactement ce que nous voulons réaliser. Pour cela, passons directement à un exemple.

On nous donne deux tableaux triés ( a et b ), qui n'ont pas nécessairement besoin d'avoir un nombre égal d'éléments:

Dans ces deux tableaux, nous voulons trouver le k e plus petit élément. Plus précisément, nous voulons trouver le k e plus petit élément du tableau combiné et trié:

Le tableau combiné et trié pour notre exemple est illustré en (c). Le premier élément le plus petit est 3 et le quatrième élément le plus petit est 20 .

2.2. Dupliquer les valeurs

Nous devrons également définir comment gérer les valeurs en double. Un élément peut apparaître plus d'une fois dans l'un des tableaux (élément 3 du tableau a ) et se reproduire également dans le deuxième tableau ( b ).

Si nous ne comptons les doublons qu'une seule fois, nous compterons comme indiqué en (c). Si nous comptons toutes les occurrences d'un élément, nous compterons comme indiqué en (d).

Dans la partie restante de cet article, nous compterons les doublons comme indiqué en (d), les comptant ainsi comme s'il s'agissait d'éléments distincts.

3. Deux approches simples mais moins efficaces

3.1. Joindre puis trier les deux tableaux

Le moyen le plus simple de trouver le k e plus petit élément est de joindre les tableaux, de les trier et de renvoyer le k e élément du tableau résultant:

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

Avec n étant la longueur du premier tableau et m la longueur du second tableau, nous obtenons la longueur combinée c = n + m .

Puisque la complexité du tri est O (c log c) , la complexité globale de cette approche est O (n log n) .

Un inconvénient de cette approche est que nous devons créer une copie du tableau, ce qui se traduit par plus d'espace nécessaire.

3.2. Fusionner les deux tableaux

Semblable à une seule étape de l'algorithme de tri Merge Sort, nous pouvons fusionner les deux tableaux, puis récupérer directement le k ème élément.

L'idée de base de l'algorithme de fusion est de commencer avec deux pointeurs, qui pointent vers les premiers éléments des premier et second tableaux (a).

Nous comparons ensuite les deux éléments ( 3 et 4 ) aux pointeurs, ajoutons le plus petit ( 3 ) au résultat et déplaçons ce pointeur d'une position vers l'avant (b). Encore une fois, nous comparons les éléments aux pointeurs et ajoutons le plus petit ( 4 ) au résultat.

Nous continuons de la même manière jusqu'à ce que tous les éléments soient ajoutés au tableau résultant. Si l'un des tableaux d'entrée n'a pas plus d'éléments, nous copions simplement tous les éléments restants de l'autre tableau d'entrée dans le tableau de résultats.

Nous pouvons améliorer les performances si nous ne copions pas les tableaux complets, mais nous arrêterons lorsque le tableau résultant contient k éléments. Nous n'avons même pas besoin de créer un tableau supplémentaire pour le tableau combiné, mais ne pouvons fonctionner que sur les tableaux d'origine.

Voici une implémentation 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]; } }

Il est simple de comprendre que la complexité temporelle de cet algorithme est O ( k ). Un avantage de cet algorithme est qu'il peut être facilement adapté pour ne considérer qu'une seule fois les éléments en double .

4. Une recherche binaire sur les deux tableaux

Pouvons-nous faire mieux que O ( k )? La réponse est que nous pouvons. L'idée de base est de faire un algorithme de recherche binaire sur les deux tableaux .

Pour que cela fonctionne, nous avons besoin d'une structure de données qui fournit un accès en lecture à temps constant à tous ses éléments. En Java, cela peut être un tableau ou une ArrayList .

Définissons le squelette de la méthode que nous allons implémenter:

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

Le dernier algorithme que nous avons vu est un bel exercice théorique; cependant, pour la plupart des raisons pratiques, nous devrions envisager d'utiliser l'un des deux premiers algorithmes, qui sont beaucoup plus simples que la recherche binaire sur deux tableaux. Bien sûr, si les performances sont un problème, une recherche binaire pourrait être une solution.

Tout le code de cet article est disponible à l'adresse over sur GitHub.