Намерете Kth най-малкия елемент в два сортирани масива в Java

1. Въведение

В тази статия ще видим как да намерим k -тия най-малък елемент в обединението на два сортирани масива.

Първо ще определим точния проблем. Второ, ще видим две неефективни, но ясни решения. Трето, ще разгледаме ефективно решение, базирано на двоично търсене на двата масива. Накрая ще разгледаме някои тестове, за да проверим дали алгоритъмът ни работи.

Ще видим и фрагменти на Java код за всички части на алгоритъма. За по-простота, нашето внедряване ще работи само върху цели числа . Описаният алгоритъм обаче работи с всички типове данни, които са сравними и дори биха могли да бъдат внедрени с помощта на Generics.

2. Каква е K -ти-малък елемент в Съюза на две Подредено Масивите?

2.1. В К -ти малък елемент

За да намерим k -тия най-малък елемент, наричан още k -та статистика от порядъка, в масив, обикновено използваме алгоритъм за избор. Тези алгоритми обаче работят на един несортиран масив, докато в тази статия искаме да намерим k -тия най-малък елемент в два сортирани масива.

Преди да видим няколко решения на проблема, нека дефинираме точно какво искаме да постигнем. За това нека да преминем направо към пример.

Дадени са ни два сортирани масива ( a и b ), които не е задължително да имат равен брой елементи:

В тези два масива искаме да намерим k -тия най-малък елемент. По-конкретно, искаме да намерим k -тия най-малък елемент в комбинирания и сортиран масив:

Комбинираният и сортиран масив за нашия пример е показан в (c). В първата най-малкия елемент е 3 , а 4-ти най-малкият елемент е 20 .

2.2. Дублирани стойности

Също така ще трябва да определим как да обработваме дублиращи се стойности. Елемент може да се появи повече от веднъж в един от масивите (елемент 3 в масив а ) и също така да се появи отново във втория масив ( b ).

Ако броим дубликати само веднъж, ще броим, както е показано в (c). Ако преброим всички появявания на елемент, ще броим, както е показано в (d).

В останалата част на тази статия ще преброим дубликати, както е показано в (d), като по този начин ги броим, като че ли са отделни елементи.

3. Два прости, но по-малко ефективни подхода

3.1. Присъединете се и след това сортирайте двата масива

Най-простият начин да намерите k -тия най-малък елемент е да се присъедините към масивите, да ги сортирате и да върнете k -тия елемент на получения масив:

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

Тъй като n е дължината на първия масив, а m дължината на втория масив, получаваме комбинираната дължина c = n + m .

Тъй като сложността за сортирането е O (c log c) , общата сложност на този подход е O (n log n) .

Недостатък на този подход е, че трябва да създадем копие на масива, което води до повече пространство.

3.2. Обединете двата масива

Подобно на една единствена стъпка от алгоритъма за сортиране Merge Sort, можем да обединим двата масива и след това директно да извлечем k -тия елемент.

Основната идея на алгоритъма за сливане е да започне с два указателя, които сочат към първите елементи на първия и втория масив (а).

След това сравняваме двата елемента ( 3 и 4 ) в указателите, добавяме по-малкия ( 3 ) към резултата и преместваме този указател с една позиция напред (b). Отново сравняваме елементите в указателите и добавяме по-малкия ( 4 ) към резултата.

Продължаваме по същия начин, докато всички елементи се добавят към получения масив. Ако един от входните масиви няма повече елементи, ние просто копираме всички останали елементи от другия масив за въвеждане в масива с резултати.

Можем да подобрим производителността, ако не копираме пълните масиви, но спираме, когато полученият масив има k елемента. Дори не е необходимо да създаваме допълнителен масив за комбинирания масив, но можем да работим само с оригиналните масиви.

Ето изпълнение в 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]; } }

Ясно е да се разбере, че сложността във времето на този алгоритъм е O ( k ). Предимство на този алгоритъм е, че той може лесно да бъде адаптиран да разглежда дублиращи се елементи само веднъж .

4. Двоично търсене на двата масива

Можем ли да се справим по-добре от O ( k )? Отговорът е, че можем. Основната идея е да се направи двоичен алгоритъм за търсене върху двата масива .

За да работи това, ние се нуждаем от структура от данни, която осигурява постоянен достъп за четене до всички негови елементи. В Java това може да е масив или ArrayList .

Нека дефинираме скелета за метода, който ще приложим:

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

Последният алгоритъм, който видяхме, е хубаво теоретично упражнение; за повечето практически цели обаче трябва да обмислим използването на един от първите два алгоритма, които са много по-прости от бинарното търсене в два масива. Разбира се, ако производителността е проблем, бинарното търсене може да бъде решение.

Целият код в тази статия е достъпен в GitHub.