1. Gambaran keseluruhan
Dalam tutorial ini, kita akan melihat algoritma yang berbeza yang membolehkan kita mencari bilangan bulat positif terkecil yang hilang dalam satu array.
Pertama, kita akan menerangkan masalahnya. Selepas itu, kita akan melihat tiga algoritma berbeza yang sesuai dengan keperluan kita. Akhirnya, kita akan membincangkan kerumitan mereka.
2. Penjelasan Masalah
Pertama, mari terangkan apa tujuan algoritma. Kami ingin mencari bilangan bulat positif terkecil yang hilang dalam pelbagai bilangan bulat positif. Maksudnya, dalam susunan elemen x , cari elemen terkecil antara 0 dan x - 1 yang tidak terdapat dalam larik. Sekiranya array mengandungi semuanya, maka penyelesaiannya adalah x , ukuran array.
Sebagai contoh, mari kita pertimbangkan susunan berikut: [0, 1, 3, 5, 6] . Ia mempunyai 5 elemen. Ini bermaksud kita mencari bilangan bulat terkecil antara 0 dan 4 yang tidak terdapat dalam larik ini. Dalam kes khusus ini, ia adalah 2 .
Sekarang, mari kita bayangkan susunan lain: [0, 1, 2, 3] . Oleh kerana ia mempunyai 4 elemen, kami mencari bilangan bulat antara 0 dan 3 . Tidak ada yang hilang, oleh itu bilangan bulat terkecil yang tidak terdapat dalam array ialah 4 .
3. Susun Susun
Sekarang, mari kita lihat bagaimana mencari nombor terkecil yang hilang dalam susunan yang disusun. Dalam susunan yang disusun, bilangan bulat terkecil yang hilang adalah indeks pertama yang tidak memiliki nilai.
Mari pertimbangkan susunan yang disusun berikut: [0, 1, 3, 4, 6, 7] . Sekarang, mari kita lihat nilai mana yang sesuai dengan indeks mana:
Index: 0 1 2 3 4 5 Value: 0 1 3 4 6 7Seperti yang kita lihat, indeks nilai tidak memegang bilangan bulat 2 , oleh itu 2 adalah bilangan bulat terkecil yang hilang dalam array.
Bagaimana dengan menerapkan algoritma ini di Java? Mari buat kelas pertama SmallestMissingPositiveInteger dengan kaedah searchInSortedArray () :
public class SmallestMissingPositiveInteger { public static int searchInSortedArray(int[] input) { // ... } }Sekarang, kita boleh melakukan iterasi pada array dan mencari indeks pertama yang tidak mengandung dirinya sebagai nilai dan mengembalikannya sebagai hasilnya:
for (int i = 0; i < input.length; i++) { if (i != input[i]) { return i; } }Akhirnya, jika kita melengkapkan gelung tanpa mencari unsur yang hilang, kita mesti mengembalikan bilangan bulat seterusnya, yang merupakan panjang array , ketika kita mulai di indeks 0 :
return input.length;Mari kita periksa bahawa ini semua berfungsi seperti yang diharapkan. Bayangkan pelbagai bilangan bulat dari 0 hingga 5 , dengan nombor 3 hilang:
int[] input = new int[] {0, 1, 2, 4, 5};Kemudian, jika kita mencari bilangan bulat pertama yang hilang, 3 harus dikembalikan:
int result = SmallestMissingPositiveInteger.searchInSortedArray(input); assertThat(result).isEqualTo(3);Tetapi, jika kita mencari nombor yang hilang dalam array tanpa bilangan bulat yang hilang:
int[] input = new int[] {0, 1, 2, 3, 4, 5};Kita akan dapati bahawa bilangan bulat pertama yang hilang adalah 6 , yang merupakan panjang array:
int result = SmallestMissingPositiveInteger.searchInSortedArray(input); assertThat(result).isEqualTo(input.length);Seterusnya, kita akan melihat bagaimana menangani susunan yang tidak disusun.
4. Array yang tidak disusun
Jadi, bagaimana dengan mencari bilangan bulat terkecil yang hilang dalam susunan yang tidak disusun? Terdapat pelbagai penyelesaian. Yang pertama ialah menyusun susunan terlebih dahulu dan kemudian menggunakan semula algoritma sebelumnya. Pendekatan lain adalah menggunakan array lain untuk menandakan bilangan bulat yang ada dan kemudian melintasi tatasusunan itu untuk mencari yang pertama hilang.
4.1. Menyusun Array Pertama
Mari mulakan dengan penyelesaian pertama dan buat kaedah searchInUnsortedArraySortingFirst () baru .
Oleh itu, kami akan menggunakan semula algoritma kami, tetapi pertama, kami perlu menyusun susunan input kami. Untuk melakukannya, kami akan menggunakan Arrays.sort () :
Arrays.sort(input);Kaedah itu menyusun input mengikut susunan semula jadi. Untuk bilangan bulat, itu bermaksud dari yang terkecil hingga yang paling besar. Terdapat lebih banyak perincian mengenai penyortiran algoritma dalam artikel kami mengenai menyusun susunan di Java.
Selepas itu, kami dapat memanggil algoritma kami dengan input yang sekarang disusun:
return searchInSortedArray(input);Itu sahaja, kita sekarang dapat memeriksa bahawa semuanya berfungsi seperti yang diharapkan. Mari bayangkan susunan berikut dengan bilangan bulat yang tidak disusun dan nombor 1 dan 3 yang hilang :
int[] input = new int[] {4, 2, 0, 5};Oleh kerana 1 adalah bilangan bulat terkecil yang hilang, kami menjangkakan ia adalah hasil memanggil kaedah kami:
int result = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst(input); assertThat(result).isEqualTo(1);Sekarang, mari kita mencuba pada array tanpa nombor yang hilang:
int[] input = new int[] {4, 5, 1, 3, 0, 2}; int result = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst(input); assertThat(result).isEqualTo(input.length);Itu sahaja, algoritma mengembalikan 6 , iaitu panjang array.
4.2. Menggunakan Array Boolean
Kemungkinan lain adalah menggunakan array lain - mempunyai panjang yang sama dengan array input - yang menyimpan nilai boolean yang memberitahu apakah bilangan bulat yang sesuai dengan indeks telah dijumpai dalam array input atau tidak.
Pertama, mari buat kaedah ketiga, searchInUnsortedArrayBooleanArray () .
After that, let's create the boolean array, flags, and for each integer in the input array that matches an index of the boolean array, we set the corresponding value to true:
boolean[] flags = new boolean[input.length]; for (int number : input) { if (number < flags.length) { flags[number] = true; } }Now, our flags array holds true for each integer present in the input array, and false otherwise. Then, we can iterate over the flags array and return the first index holding false. If none, we return the array length:
for (int i = 0; i < flags.length; i++) { if (!flags[i]) { return i; } } return flags.length;Again, let's try this algorithm with our examples. We'll first reuse the array missing 1 and 3:
int[] input = new int[] {4, 2, 0, 5};Then, when searching for the smallest missing integer with our new algorithm, the answer is still 1:
int result = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray(input); assertThat(result).isEqualTo(1);And for the complete array, the answer doesn't change either and is still 6:
int[] input = new int[] {4, 5, 1, 3, 0, 2}; int result = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray(input); assertThat(result).isEqualTo(input.length);5. Complexities
Now that we've covered the algorithms, let's talk about their complexities, using Big O notation.
5.1. Sorted Array
Let's start with the first algorithm, for which the input is already sorted. In this case, the worst-case scenario is not finding a missing integer and, therefore, traversing the entire array. This means we have linear complexity, which is noted O(n), considering n is the length of our input.
5.2. Unsorted Array with Sorting Algorithm
Now, let's consider our second algorithm. In this case, the input array is not sorted, and we sort it before applying the first algorithm. Here, the complexity will be the greatest between that of the sorting mechanism and that of the algorithm itself.
As of Java 11, the Arrays.sort() method uses a dual-pivot quick-sort algorithm to sort arrays. The complexity of this sorting algorithm is, in general, O(n log(n)), though it could degrade up to O(n²). That means the complexity of our algorithm will be O(n log(n)) in general and can also degrade up to a quadratic complexity of O(n²).
That's for time complexity, but let's not forget about space. Although the search algorithm doesn't take extra space, the sorting algorithm does. Quick-sort algorithm takes up to O(log(n)) space to execute. That's something we may want to consider when choosing an algorithm for large arrays.
5.3. Unsorted Array with Boolean Array
Finally, let's see how our third and last algorithm performs. For this one, we don't sort the input array, which means we don't suffer the complexity of sorting. As a matter of fact, we only traverse two arrays, both of the same size. That means our time complexity should be O(2n), which is simplified to O(n). That's better than the previous algorithm.
Tetapi, mengenai kerumitan ruang, kami membuat susunan kedua dengan ukuran yang sama dengan input. Ini bermakna kita mempunyai kerumitan ruang O (n) , yang lebih buruk daripada algoritma sebelumnya.
Mengetahui semua itu, kita harus memilih algoritma yang paling sesuai dengan keperluan kita, bergantung kepada keadaan di mana ia akan digunakan.
6. Kesimpulannya
Dalam artikel ini, kami telah melihat algoritma untuk mencari bilangan bulat positif terkecil yang hilang dalam suatu array. Kami telah melihat bagaimana mencapainya dalam susunan yang disusun, dan juga dalam susunan yang tidak disusun. Kami juga membincangkan kerumitan masa dan ruang dari algoritma yang berbeza, yang membolehkan kami memilih satu dengan bijak mengikut keperluan kami.
Seperti biasa, contoh kod lengkap yang ditunjukkan dalam artikel ini terdapat di GitHub.