Tìm phần tử nhỏ nhất thứ K trong hai mảng đã sắp xếp bằng Java

1. Giới thiệu

Trong bài viết này, chúng ta sẽ xem cách tìm phần tử thứ k nhỏ nhất trong hợp của hai mảng đã sắp xếp.

Đầu tiên, chúng tôi sẽ xác định vấn đề chính xác. Thứ hai, chúng ta sẽ thấy hai giải pháp không hiệu quả nhưng đơn giản. Thứ ba, chúng ta sẽ xem xét một giải pháp hiệu quả dựa trên tìm kiếm nhị phân trên hai mảng. Cuối cùng, chúng tôi sẽ xem xét một số thử nghiệm để xác minh rằng thuật toán của chúng tôi hoạt động.

Chúng ta cũng sẽ thấy các đoạn mã Java cho tất cả các phần của thuật toán. Để đơn giản, việc triển khai của chúng tôi sẽ chỉ hoạt động trên các số nguyên . Tuy nhiên, thuật toán được mô tả hoạt động với tất cả các kiểu dữ liệu có thể so sánh được và thậm chí có thể được triển khai bằng Generics.

2. Phần tử nhỏ nhất thứ K trong Liên minh của hai mảng đã sắp xếp là gì?

2.1. Các K thứ nhỏ tử

Để tìm phần tử nhỏ nhất thứ k , còn được gọi là thống kê bậc k , trong một mảng, chúng ta thường sử dụng một thuật toán lựa chọn. Tuy nhiên, các thuật toán này hoạt động trên một mảng duy nhất, không được sắp xếp, trong khi trong bài viết này, chúng tôi muốn tìm phần tử nhỏ nhất thứ k trong hai mảng đã sắp xếp.

Trước khi chúng ta thấy một số giải pháp cho vấn đề, hãy xác định chính xác những gì chúng ta muốn đạt được. Đối với điều đó, chúng ta hãy chuyển ngay sang một ví dụ.

Chúng ta được cung cấp hai mảng đã sắp xếp ( ab ), không nhất thiết phải có số phần tử bằng nhau:

Trong hai mảng này, chúng ta muốn tìm phần tử nhỏ nhất thứ k . Cụ thể hơn, chúng ta muốn tìm phần tử nhỏ nhất thứ k trong mảng được kết hợp và sắp xếp:

Mảng được kết hợp và sắp xếp cho ví dụ của chúng ta được hiển thị trong (c). Phần tử nhỏ nhất đầu tiên3 và phần tử nhỏ nhất thứ 420 .

2.2. Giá trị trùng lặp

Chúng tôi cũng sẽ cần xác định cách xử lý các giá trị trùng lặp. Một phần tử có thể xuất hiện nhiều lần trong một trong các mảng (phần tử 3 trong mảng a ) và cũng có thể xảy ra lại trong mảng thứ hai ( b ).

Nếu chúng tôi chỉ đếm các bản sao một lần, chúng tôi sẽ tính như trong (c). Nếu chúng tôi đếm tất cả các lần xuất hiện của một phần tử, chúng tôi sẽ tính như được hiển thị trong (d).

Trong phần còn lại của bài viết này, chúng tôi sẽ đếm các bản sao như được hiển thị trong (d), do đó đếm chúng như thể chúng là các phần tử riêng biệt.

3. Hai cách tiếp cận đơn giản nhưng kém hiệu quả

3.1. Tham gia và sau đó sắp xếp hai mảng

Cách đơn giản nhất để tìm phần tử nhỏ nhất thứ k là nối các mảng, sắp xếp chúng và trả về phần tử thứ k của mảng kết quả:

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

Với n là độ dài của mảng thứ nhất và m là độ dài của mảng thứ hai, ta nhận được độ dài kết hợp c = n + m .

Vì độ phức tạp của sắp xếp là O (c log c) , độ phức tạp tổng thể của phương pháp này là O (n log n) .

Một nhược điểm của phương pháp này là chúng ta cần tạo một bản sao của mảng, điều này dẫn đến cần nhiều không gian hơn.

3.2. Hợp nhất hai mảng

Tương tự như một bước duy nhất của thuật toán sắp xếp Merge Sort, chúng ta có thể hợp nhất hai mảng và sau đó lấy trực tiếp phần tử thứ k .

Ý tưởng cơ bản của thuật toán hợp nhất là bắt đầu với hai con trỏ trỏ đến phần tử đầu tiên của mảng thứ nhất và mảng thứ hai (a).

Sau đó, chúng tôi so sánh hai phần tử ( 34 ) tại các con trỏ, thêm phần tử nhỏ hơn ( 3 ) vào kết quả, và di chuyển con trỏ đó về phía trước một vị trí (b). Một lần nữa, chúng tôi so sánh các phần tử tại các con trỏ và thêm phần tử nhỏ hơn ( 4 ) vào kết quả.

Chúng tôi tiếp tục theo cách tương tự cho đến khi tất cả các phần tử được thêm vào mảng kết quả. Nếu một trong các mảng đầu vào không có nhiều phần tử hơn, chúng ta chỉ cần sao chép tất cả các phần tử còn lại của mảng đầu vào khác vào mảng kết quả.

Chúng ta có thể cải thiện hiệu suất nếu chúng ta không sao chép đầy đủ các mảng, nhưng dừng lại khi mảng kết quả có k phần tử. Chúng tôi thậm chí không cần tạo thêm một mảng cho mảng kết hợp mà chỉ có thể hoạt động trên các mảng ban đầu.

Đây là một triển khai trong 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]; } }

Thật đơn giản để hiểu độ phức tạp thời gian của thuật toán này là O ( k ). Một ưu điểm của thuật toán này là nó có thể dễ dàng điều chỉnh để xem xét các phần tử trùng lặp chỉ một lần .

4. Tìm kiếm nhị phân trên cả hai mảng

Chúng ta có thể làm tốt hơn O ( k ) không? Câu trả lời là chúng ta có thể. Ý tưởng cơ bản là thực hiện một thuật toán tìm kiếm nhị phân trên hai mảng .

Để điều này hoạt động, chúng ta cần một cấu trúc dữ liệu cung cấp quyền truy cập đọc trong thời gian liên tục cho tất cả các phần tử của nó. Trong Java, đó có thể là một mảng hoặc ArrayList .

Hãy xác định khung cho phương thức chúng ta sẽ triển khai:

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

Ở đây, chúng ta chuyển k và hai mảng làm đối số. Đầu tiên, chúng tôi sẽ xác nhận đầu vào; thứ hai, chúng tôi xử lý một số trường hợp đặc biệt và sau đó thực hiện tìm kiếm nhị phân. Trong ba phần tiếp theo, chúng ta sẽ xem xét ba bước này theo thứ tự ngược lại, vì vậy, đầu tiên, chúng ta sẽ xem tìm kiếm nhị phân, thứ hai, các trường hợp đặc biệt và cuối cùng, xác thực tham số.

4.1. Tìm kiếm nhị phân

Tìm kiếm nhị phân tiêu chuẩn, nơi chúng tôi đang tìm kiếm một phần tử cụ thể, có hai kết quả có thể xảy ra: hoặc chúng tôi tìm thấy phần tử mà chúng tôi đang tìm kiếm và tìm kiếm thành công, hoặc chúng tôi không tìm thấy nó và tìm kiếm không thành công. Điều này khác với trường hợp của chúng ta, khi chúng ta muốn tìm phần tử nhỏ nhất thứ k . Ở đây, chúng ta luôn có một kết quả.

Hãy xem cách thực hiện điều đó.

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

Thuật toán cuối cùng mà chúng ta thấy là một bài tập lý thuyết hay; tuy nhiên, đối với hầu hết các mục đích thực tế, chúng ta nên cân nhắc sử dụng một trong hai thuật toán đầu tiên, đơn giản hơn nhiều so với tìm kiếm nhị phân trên hai mảng. Tất nhiên, nếu hiệu suất là một vấn đề, tìm kiếm nhị phân có thể là một giải pháp.

Tất cả mã trong bài viết này đều có sẵn trên GitHub.