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>
   Predefined array:
   <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)，与二分查找方法相同。

这种方法比线性搜索方法更高效，并且要求数组已排序。