数据结构
网络
关系数据库管理系统
操作系统
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 次查看
