Kami mendapat tatasusunan diisih integer bukan negatif yang berbeza, di sini kami perlu mencari nombor terkecil yang hilang. Oleh itu, dalam tutorial ini, kami akan meneroka cara yang berbeza untuk menyelesaikan masalah ini dan membincangkan kerumitan masanya dengan pelbagai contoh.
Huraian masalah sangat mudah. Memandangkan tatasusunan diisih integer bukan negatif yang berbeza, kita perlu mencari nombor terkecil yang hilang di dalamnya. Mari kita ambil contoh untuk memahami masalah ini.
Katakan kita mempunyai tatasusunan [1, 2, 4, 5, 6]. Di sini kita dapat melihat bahawa terdapat ruang antara nombor 2 dan 4 dalam tatasusunan ini. Percanggahan ini menunjukkan bahawa nombor tiada. Sekarang kita perlu mencari nombor terkecil yang sesuai dengan kedudukan.
Untuk menentukan sama ada nombor tiada, pertama sekali kita perlu melihat sama ada tatasusunan mengandungi nombor 3. Jika nombor 3 tidak wujud dalam tatasusunan, kita boleh mengatakan bahawa ia adalah nombor yang hilang kerana nombor 3 tidak terkandung dalam tatasusunan.
Sekarang mari kita lihat beberapa cara untuk menyelesaikan masalah ini.
Salah satu cara paling mudah untuk menyelesaikan masalah ini ialah dengan mengulang tatasusunan dan pastikan setiap item berada dalam kedudukan yang betul. Jika elemen tidak berada dalam kedudukan yang betul, kita dapati bilangan minimum elemen yang hilang.
Ini adalah kod yang dijelaskan di atas -
<!DOCTYPE html>
<html>
<body>
<h2>Find Smallest Missing Number</h2>
<p>Array: [0, 1, 2, 3, 5, 6]</p>
<p>Result: <span id="result"></span></p>
<script>
function findSmallestMissingNumber(arr) {
let n = arr.length;
for (let i = 0; i < n; i++) {
if (arr[i] !== i) {
return i;
}
}
return n;
}
const arr = [0, 1, 2, 3, 5, 6];
const result = findSmallestMissingNumber(arr);
document.getElementById("result").innerHTML = result;
</script>
</body>
</html>
Memandangkan kita menggelung seluruh tatasusunan, kerumitan masa kaedah ini ialah O(n).
Walau bagaimanapun, penyelesaian ini tidak cekap kerana ia tidak mengambil kesempatan daripada fakta bahawa kami diberi tatasusunan yang disusun.
Di sini, kami akan menggunakan kaedah carian binari untuk menyelesaikan masalah ini dengan lebih cekap. Dalam kaedah ini kami melakukan carian binari untuk elemen pertama yang tidak terdapat dalam tatasusunan. Kod untuk kaedah ini ialah -
<!DOCTYPE html>
<html>
<body>
<div id="result"></div>
<script>
function findSmallestMissingNumber(arr) {
let n = arr.length;
let low = 0;
let high = n - 1;
let mid = 0;
while (high - low > 1) {
mid = Math.floor((low + high) / 2);
if (arr[mid] - mid !== arr[low] - low) {
high = mid;
} else if (arr[mid] - mid !== arr[high] - high) {
low = mid;
}
}
return arr[low] + 1;
}
const arr = [0, 1, 2, 3, 4, 5, 6, 8];
const result = findSmallestMissingNumber(arr);
document.getElementById("result").innerHTML = "Array: " + JSON.stringify(arr) ;
document.getElementById("result").innerHTML += "<br>The smallest missing number is: " + result;
</script>
</body>
</html>
Oleh kerana kami melakukan carian binari, kerumitan masa kaedah di atas ialah O(log n).
Kaedah ini lebih cekap daripada kaedah mudah kami kerana ia mengambil kesempatan daripada fakta bahawa tatasusunan disusun.
Kaedah ketiga yang akan kita bincangkan ialah kaedah carian linear. Kaedah ini bergantung pada fakta bahawa tatasusunan diisih, yang akan membolehkan kami menggunakan carian linear untuk mengenal pasti nombor yang hilang.
Kaedah carian linear berfungsi dengan mengulangi tatasusunan dan membandingkan setiap ahli dengan indeksnya. Jika indeks sesuatu elemen tidak sama dengan nilainya, elemen yang hilang berada di tempat lain dalam tatasusunan sebelum elemen itu. Kami mengembalikan indeks elemen yang hilang.
Kod kaedah carian linear adalah seperti berikut -
<!DOCTYPE html>
<html>
<body>
<h2>Find Smallest Missing Number</h2>
<p>Array: [1, 2, 3, 5]</p>
<p>Result: <span id="result"></span></p>
<script>
function findSmallestMissingNumber(arr) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== i+1) {
return i+1;
}
}
return arr.length+1;
}
const arr = [1, 2, 3, 5];
const result = findSmallestMissingNumber(arr);
document.getElementById("result").innerHTML = result;
</script>
</body>
</html>
Kerumitan masa kaedah ini ialah O(n) kerana kita perlu mengulangi keseluruhan tatasusunan.
Kaedah ini kurang cekap daripada kaedah carian binari, tetapi berguna untuk tatasusunan kecil.
Kaedah keempat yang akan kita bincangkan ialah kaedah carian binari yang dipertingkatkan. Kaedah ini sangat serupa dengan kaedah carian binari, kecuali daripada membandingkan elemen tengah dengan integer yang hilang, kami membandingkannya dengan indeksnya.
Idea asas di sebalik kaedah carian binari yang diubah suai adalah untuk membahagi tatasusunan kepada separuh pada setiap langkah dan membandingkan elemen tengah dengan indeksnya. Jika elemen tengah lebih besar daripada indeksnya, ahli yang hilang mesti berada di separuh kiri tatasusunan. Jika elemen tengah sama dengan atau kurang daripada indeksnya, elemen yang hilang mestilah berada di separuh kanan tatasusunan.
Ini ialah pelaksanaan kod kaedah carian binari yang diubah suai -
<!DOCTYPE html> <html> <body> <h2>Find Smallest Missing Number</h2> <p>Predefined array:</p> <pre id="inputArray"><script> // Define the input array const inputArray = [0, 1, 2, 3, 4, 6, 7, 8]; // Display the input array in the pre tag document.getElementById("inputArray").innerHTML = JSON.stringify(inputArray); function findMissingNumber() { // Call the findSmallestMissingNumber function to get the result const result = findSmallestMissingNumber(inputArray); // Display the result using the innerHTML method document.getElementById("result").innerHTML = `The smallest missing number is: ${result}`; } // Copy the findSmallestMissingNumber function here function findSmallestMissingNumber(arr) { let left = 0; let right = arr.length - 1; while (left <= right) { let mid = Math.floor((left + right) / 2); if (arr[mid] > mid) { right = mid - 1; } else { left = mid + 1; } } return left; } </script>