Temukan Elemen Terkecil K dalam Dua Susunan Berurut di Jawa

1. Perkenalan

Dalam artikel ini, kita akan melihat bagaimana menemukan elemen terkecil ke- k dalam gabungan dua larik yang diurutkan.

Pertama, kami akan mendefinisikan masalah yang sebenarnya. Kedua, kita akan melihat dua solusi yang tidak efisien tetapi langsung. Ketiga, kita akan melihat solusi yang efisien berdasarkan pencarian biner pada dua larik. Terakhir, kita akan melihat beberapa tes untuk memverifikasi bahwa algoritma kita berfungsi.

Kami juga akan melihat cuplikan kode Java untuk semua bagian algoritme. Untuk kesederhanaan, implementasi kami hanya akan beroperasi pada bilangan bulat . Namun, algoritma yang dijelaskan bekerja dengan semua tipe data yang sebanding dan bahkan dapat diimplementasikan menggunakan Generik.

2. Apa Elemen Terkecil ke- K dalam Gabungan Dua Array Berurut?

2.1. The K unsur Terkecil

Untuk mencari elemen terkecil ke- k , juga disebut statistik orde- k ke- k , dalam sebuah larik, kita biasanya menggunakan algoritma pemilihan. Namun, algoritma ini beroperasi pada array tunggal yang tidak disortir, sedangkan pada artikel ini, kita ingin mencari elemen terkecil ke- k dalam dua array yang diurutkan.

Sebelum kita melihat beberapa solusi untuk masalah ini, mari kita definisikan dengan tepat apa yang ingin kita capai. Untuk itu, mari langsung ke contoh.

Kami diberi dua larik terurut ( a dan b ), yang tidak perlu memiliki jumlah elemen yang sama:

Dalam dua larik ini, kita ingin mencari elemen terkecil ke k . Lebih khusus lagi, kami ingin mencari elemen terkecil ke- k dalam array yang digabungkan dan diurutkan:

Array yang digabungkan dan diurutkan untuk contoh kita ditunjukkan di (c). Unsur terkecil ke - 1 adalah 3 , dan unsur terkecil ke - 4 adalah 20 .

2.2. Nilai Duplikat

Kami juga perlu menentukan cara menangani nilai duplikat. Sebuah elemen dapat muncul lebih dari sekali dalam salah satu larik (elemen 3 dalam larik a ) dan juga muncul lagi dalam larik kedua ( b ).

Jika kita menghitung duplikat hanya sekali, kita akan menghitung seperti yang ditunjukkan pada (c). Jika kita menghitung semua kemunculan suatu elemen, kita akan menghitung seperti yang ditunjukkan pada (d).

Di bagian sisa artikel ini, kita akan menghitung duplikat seperti yang ditunjukkan pada (d), sehingga menghitungnya seolah-olah itu adalah elemen yang berbeda.

3. Dua Pendekatan Sederhana namun Kurang Efisien

3.1. Gabung dan Kemudian Sortir Dua Array

Cara termudah untuk menemukan elemen terkecil ke- k adalah dengan menggabungkan array, mengurutkannya, dan mengembalikan elemen ke- k dari array yang dihasilkan:

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

Dengan n sebagai panjang larik pertama dan m panjang larik kedua, kita mendapatkan gabungan panjang c = n + m .

Karena kompleksitas untuk jenisnya adalah O (c log c) , kompleksitas keseluruhan dari pendekatan ini adalah O (n log n) .

Kerugian dari pendekatan ini adalah kita perlu membuat salinan larik, yang menghasilkan lebih banyak ruang yang dibutuhkan.

3.2. Gabungkan Dua Array

Mirip dengan satu langkah algoritma pengurutan Merge Sort, kita dapat menggabungkan dua array dan kemudian langsung mengambil elemen k .

Ide dasar dari algoritma penggabungan adalah memulai dengan dua pointer, yang menunjuk ke elemen pertama dari array pertama dan kedua (a).

Kami kemudian membandingkan dua elemen ( 3 dan 4 ) pada pointer, menambahkan yang lebih kecil ( 3 ) ke hasil, dan memindahkan pointer satu posisi ke depan (b). Sekali lagi, kami membandingkan elemen pada pointer dan menambahkan yang lebih kecil ( 4 ) ke hasilnya.

Kami melanjutkan dengan cara yang sama sampai semua elemen ditambahkan ke array yang dihasilkan. Jika salah satu larik input tidak memiliki lebih banyak elemen, kita cukup menyalin semua elemen yang tersisa dari larik masukan lainnya ke larik hasil.

Kita dapat meningkatkan kinerja jika kita tidak menyalin larik penuh, tetapi berhenti ketika larik yang dihasilkan memiliki k elemen. Kita bahkan tidak perlu membuat larik tambahan untuk larik gabungan tetapi bisa beroperasi hanya pada larik asli.

Berikut implementasinya di 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]; } }

Sangat mudah untuk memahami kompleksitas waktu dari algoritma ini adalah O ( k ). Keuntungan dari algoritma ini adalah dapat dengan mudah diadaptasi untuk mempertimbangkan elemen duplikat hanya sekali .

4. Pencarian Biner Atas Kedua Array

Bisakah kita melakukan lebih baik dari O ( k )? Jawabannya adalah kita bisa. Ide dasarnya adalah melakukan algoritma pencarian biner pada dua array .

Agar ini berfungsi, kita memerlukan struktur data yang menyediakan akses baca waktu-konstan ke semua elemennya. Di Java, itu bisa berupa array atau ArrayList .

Mari tentukan kerangka untuk metode yang akan kita terapkan:

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

Algoritme terakhir yang kami lihat adalah latihan teoretis yang bagus; namun, untuk sebagian besar tujuan praktis, kita harus mempertimbangkan menggunakan salah satu dari dua algoritme pertama, yang jauh lebih sederhana daripada pencarian biner pada dua larik. Tentu saja, jika kinerja menjadi masalah, pencarian biner bisa menjadi solusi.

Semua kode dalam artikel ini tersedia di GitHub.