資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究查詢最小缺失數的 JavaScript 程式
給定一個排序的不同非負整數陣列，我們需要找到最小的缺失數字。因此，在本教程中，我們將探討解決此問題不同方法，並討論其在各種示例中的時間複雜度。
理解問題
問題陳述非常簡單。給定一個排序的不同非負整數陣列，我們需要找到其中最小的缺失數字。讓我們舉一個例子來理解這個問題。
示例
假設我們有一個數組 [1, 2, 4, 5, 6]。在這裡，我們可以看到在這個陣列中數字 2 和 4 之間有一個空隙。這個差異表明有一個數字丟失了。現在我們必須找到最適合放在那個位置的數字。
要確定是否存在缺失的數字，我們必須首先檢視數字 3 是否包含在陣列中。如果數字 3 不在陣列中，我們可以說它是一個缺失的數字，因為數字 3 不包含在陣列中。
現在讓我們看看一些解決此問題的方法。
方法 1：樸素方法
解決此問題最簡單的方法之一是迴圈遍歷陣列並確保每個專案都位於正確的位置。如果元素不在其正確的位置，我們將發現最小的缺失數字。
示例
以下是上述解釋的程式碼 -
<!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>
由於我們正在遍歷整個陣列，因此此方法的時間複雜度為 O(n)。
但是，此解決方案效率低下，因為它沒有利用“我們提供了排序陣列”這一事實。
方法 2：二分查詢方法
在這裡，我們將使用二分查詢方法來更有效地解決此問題。在這種方法中，我們對陣列中不存在的第一個元素進行二分查詢。此方法的程式碼如下 -
示例
<!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>
上述方法的時間複雜度為 O(log n)，因為我們正在進行二分查詢。
這種方法比我們的樸素方法更有效，因為它利用了陣列已排序的事實。
方法 3：線性搜尋方法
我們將討論的第三種方法是線性搜尋方法。此方法依賴於陣列已排序的事實，這將使我們能夠應用線性搜尋來識別缺失的數字。
線性搜尋方法透過迭代遍歷陣列並將每個成員與其索引進行比較來工作。如果元素的索引與其值不相等，則缺失的元素位於其之前的陣列中的其他位置。我們返回缺失元素的索引。
示例
線性搜尋方法的程式碼如下 -
<!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>
此方法的時間複雜度為 O(n)，因為我們正在遍歷整個陣列。
此方法不如二分查詢方法有效，但對於小型陣列很有用。
方法 4：修改後的二分查詢
我們將討論的第四種方法是修改後的二分查詢方法。此方法與二分查詢方法非常相似，只是我們不是將中間元素與缺失整數進行比較，而是將其與它的索引進行比較。
修改後的二分查詢方法背後的基本思想是在每一步都將陣列分成兩半，並將中間元素與其索引進行比較。如果中間元素大於其索引，則缺失的成員必須位於陣列的左半部分。如果中間元素等於或小於其索引，則缺失的元素必須位於陣列的右半部分。
示例
以下是修改後的二分查詢方法的程式碼實現 -
<!DOCTYPE html>
<html>
<body>
<h2>Find Smallest Missing Number</h2>
<p>Predefined array:</p>
<pre id="inputArray"></pre>
<button onclick="findMissingNumber()">Find Missing Number</button>
<p id="result"></p>
<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>
</body>
</html>
此方法的時間複雜度也為 O(log n)，與二分查詢方法相同。
此方法比線性搜尋方法更有效，並且需要陣列已排序。
結論
在本博文中，我們討論了四種從陣列中查詢最小缺失數字的方法。它們是樸素方法、二分查詢方法、線性搜尋方法和修改後的二分查詢方法。
298 次檢視
