Finden Sie das K-te kleinste Element in zwei sortierten Arrays in Java

1. Einleitung

In diesem Artikel erfahren Sie, wie Sie das k -kleinste Element in der Vereinigung zweier sortierter Arrays finden.

Zuerst definieren wir das genaue Problem. Zweitens sehen wir zwei ineffiziente, aber unkomplizierte Lösungen. Drittens werden wir uns eine effiziente Lösung ansehen, die auf einer binären Suche auf den beiden Arrays basiert. Schließlich werden wir uns einige Tests ansehen, um zu überprüfen, ob unser Algorithmus funktioniert.

Wir werden auch Java-Code-Schnipsel für alle Teile des Algorithmus sehen. Der Einfachheit halber arbeitet unsere Implementierung nur mit ganzen Zahlen . Der beschriebene Algorithmus funktioniert jedoch mit allen Datentypen, die vergleichbar sind und sogar mit Generics implementiert werden könnten.

2. Was ist das k -kleinste Element in der Vereinigung zweier sortierter Arrays?

2.1. Das K -kleinste Element

Um das k -kleinste Element, auch als Statistik der k- ten Ordnung bezeichnet, in einem Array zu finden, verwenden wir normalerweise einen Auswahlalgorithmus. Diese Algorithmen arbeiten jedoch mit einem einzelnen, unsortierten Array, während wir in diesem Artikel das k- te kleinste Element in zwei sortierten Arrays finden möchten .

Bevor wir verschiedene Lösungen für das Problem sehen, definieren wir genau, was wir erreichen wollen. Lassen Sie uns dazu gleich in ein Beispiel springen.

Wir erhalten zwei sortierte Arrays ( a und b ), die nicht unbedingt die gleiche Anzahl von Elementen haben müssen:

In diesen beiden Arrays wollen wir das k -kleinste Element finden. Insbesondere möchten wir das k -kleinste Element im kombinierten und sortierten Array finden:

Das kombinierte und sortierte Array für unser Beispiel ist in (c) gezeigt. Das 1. kleinste Element ist 3 und das 4. kleinste Element ist 20 .

2.2. Doppelte Werte

Wir müssen auch definieren, wie mit doppelten Werten umgegangen werden soll. Ein Element kann in einem der Arrays mehrmals vorkommen (Element 3 in Array a ) und auch im zweiten Array ( b ) erneut vorkommen.

Wenn wir Duplikate nur einmal zählen, zählen wir wie in (c) gezeigt. Wenn wir alle Vorkommen eines Elements zählen, zählen wir wie in (d) gezeigt.

Im verbleibenden Teil dieses Artikels zählen wir Duplikate wie in (d) gezeigt und zählen sie so, als wären sie unterschiedliche Elemente.

3. Zwei einfache, aber weniger effiziente Ansätze

3.1. Verbinden Sie die beiden Arrays und sortieren Sie sie

Der einfachste Weg, das k -kleinste Element zu finden, besteht darin, die Arrays zu verbinden, zu sortieren und das k- te Element des resultierenden Arrays zurückzugeben:

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

Wenn n die Länge des ersten Arrays und m die Länge des zweiten Arrays ist, erhalten wir die kombinierte Länge c = n + m .

Da die Komplexität für die Sortierung O (c log c) ist , ist die Gesamtkomplexität dieses Ansatzes O (n log n) .

Ein Nachteil dieses Ansatzes besteht darin, dass wir eine Kopie des Arrays erstellen müssen, wodurch mehr Platz benötigt wird.

3.2. Führen Sie die beiden Arrays zusammen

Ähnlich wie in einem einzelnen Schritt des Sortieralgorithmus "Sortierung zusammenführen" können wir die beiden Arrays zusammenführen und dann das k- te Element direkt abrufen .

Die Grundidee des Zusammenführungsalgorithmus besteht darin, mit zwei Zeigern zu beginnen, die auf die ersten Elemente des ersten und des zweiten Arrays (a) zeigen.

Wir vergleichen dann die beiden Elemente ( 3 und 4 ) an den Zeigern, fügen das kleinere ( 3 ) zum Ergebnis hinzu und bewegen diesen Zeiger um eine Position nach vorne (b). Wieder vergleichen wir die Elemente an den Zeigern und fügen dem Ergebnis das kleinere ( 4 ) hinzu.

Wir fahren auf die gleiche Weise fort, bis alle Elemente zum resultierenden Array hinzugefügt wurden. Wenn eines der Eingabearrays nicht mehr Elemente enthält, kopieren wir einfach alle verbleibenden Elemente des anderen Eingabearrays in das Ergebnisarray.

Wir können die Leistung verbessern, wenn wir nicht die vollständigen Arrays kopieren, sondern aufhören, wenn das resultierende Array k Elemente enthält. Wir müssen nicht einmal ein zusätzliches Array für das kombinierte Array erstellen, sondern können nur mit den ursprünglichen Arrays arbeiten.

Here's an implementation 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]; } }

It's straightforward to understand the time-complexity of this algorithm is O(k). An advantage of this algorithm is that it can be easily adapted to consider duplicate elements only once.

4. A Binary Search Over Both Arrays

Can we do better than O(k)? The answer is that we can. The basic idea is to do a binary search algorithm over the two arrays.

For this to work, we need a data structure that provides constant-time read access to all its elements. In Java, that could be an array or an ArrayList.

Let's define the skeleton for the method we are going to implement:

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

Der letzte Algorithmus, den wir gesehen haben, ist eine schöne theoretische Übung; Für die meisten praktischen Zwecke sollten wir jedoch die Verwendung eines der ersten beiden Algorithmen in Betracht ziehen, die viel einfacher sind als die binäre Suche über zwei Arrays. Wenn die Leistung ein Problem darstellt, kann eine binäre Suche natürlich eine Lösung sein.

Der gesamte Code in diesem Artikel ist auf GitHub verfügbar.