深入解析：如何在有序数组中高效查找缺失的自然数

2026-02-07 23:02:03 0条评论 2次阅读 0人点赞

在这篇文章中，我们将深入探讨一个在算法面试和实际开发中非常经典的问题：在一个包含 1 到 n 的自然数且已排序的数组中，如何快速找到那个唯一缺失的数字？这看起来似乎是一个简单的搜索问题，但如果我们仔细分析，会发现其中蕴含着从暴力破解到二分查找优化的完整算法思路。

问题背景与分析

首先，让我们明确一下题目所给的具体条件和限制，这对于我们选择正确的算法至关重要：

  • 有序性：数组 arr[] 是按升序排列的。
  • 范围确定：数组中的元素本应包含从 INLINECODE3e6ddc8a 到 INLINECODE79fa469a 的所有整数（假设没有缺失）。
  • 缺失唯一：数组的大小实际上是 INLINECODE08fe1e32，因为只有 INLINECODE5a800927 个数字缺失了。
  • 无重复：元素是唯一的。

看到“有序”这两个字，作为经验丰富的开发者，你的脑海里应该立刻蹦出“二分查找”这个关键词。利用有序性通常能将时间复杂度从线性级别降低到对数级别。但在直接跳到最优解之前，让我们像初学者一样，从最直观的方法开始，逐步优化我们的思路。

方法一：朴素方法 – 线性搜索

最直观的想法是：既然我们知道数字的范围是 INLINECODEadc341e3 到 INLINECODEbf3b1252，那我们就可以从这个范围内逐一取出每一个数字，然后去数组里找它是否存在。

#### 核心思路

我们可以使用两个嵌套循环：

  • 外层循环：遍历自然数 INLINECODE9c6d2a11，从 INLINECODE4d41fcf9 到 n。
  • 内层循环：遍历数组 INLINECODEd608ebd2，检查 INLINECODE6ca2dbfc 是否在数组中。
  • 判断：如果在内层循环结束后发现 INLINECODE050ac848 没有出现在数组中，那么 INLINECODE403d9152 就是我们要找的缺失数字。

#### 复杂度分析

  • 时间复杂度：O(n²)。最坏的情况下（比如缺失的是 n），我们需要对每一个 i 遍历整个数组。
  • 空间复杂度：O(1)。我们只需要常数级别的额外空间。

虽然这种方法在大数据量下效率很低，但它是逻辑上最直接的实现方式。让我们看看具体的代码实现。

#### 代码实现

为了方便你理解，我们在代码中添加了详细的中文注释。

C++ 实现

#include 
#include 
using namespace std;

// 函数用于查找缺失的数字
int missingNumber(vector &arr) {
    // 注意：数组长度是 n-1，所以总共有 n 个数（1 到 n）
    int n = arr.size() + 1;

    // 外层循环：从 1 遍历到 n
    for(int i = 1; i <= n; i++){
        bool found = false;
        
        // 内层循环：检查当前数字 i 是否存在于数组中
        for(int j = 0; j < n - 1; j++){
            if(arr[j] == i) {
                found = true;
                break; // 找到了就跳出内层循环
            }
        }

        // 如果遍历完数组都没找到 i，说明 i 就是缺失的数字
        if(!found)
            return i;
    }
    return -1; // 理论上不会执行到这里
}

int main(){
    vector arr = {1, 2, 3, 4, 6, 7, 8};
    cout << "缺失的数字是: " << missingNumber(arr) << endl;
    return 0;
}

Java 实现

class MissingNumberSolution {

    static int missingNumber(int[] arr) {
        int n = arr.length + 1;

        // 外层循环：从 1 遍历到 n
        for (int i = 1; i <= n; i++) {
            boolean found = false;
            
            // 内层循环：检查当前数字 i 是否存在于数组中
            for (int j = 0; j < arr.length; j++) {
                if (arr[j] == i) {
                    found = true;
                    break;
                }
            }

            // 如果没找到，返回 i
            if (!found)
                return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 6, 7, 8};
        System.out.println("缺失的数字是: " + missingNumber(arr));
    }
}

Python 实现

def missing_number(arr):
    n = len(arr) + 1

    # 外层循环：从 1 遍历到 n
    for i in range(1, n + 1):
        found = False
        # 内层循环：检查当前数字 i 是否存在于数组中
        for j in range(len(arr)):
            if arr[j] == i:
                found = True
                break
        
        # 如果没找到，返回 i
        if not found:
            return i
    return -1

if __name__ == "__main__":
    arr = [1, 2, 3, 4, 6, 7, 8]
    print(f"缺失的数字是: {missing_number(arr)}")

方法二：更优方法 1 – 索引与元素的差值法

既然我们上面提到数组是有序的，那么朴素方法中的内层循环其实是一种浪费。对于一个有序数组，我们不需要每次都从头到尾搜索。

#### 核心思路

让我们观察一下索引（Index）和元素值之间的关系。如果没有任何数字缺失，对于数组 arr[0...n-1]，应该满足以下规律：

  • arr[0] 应该是 1
  • arr[1] 应该是 2
  • …
  • INLINECODE9bfb9a12 应该是 INLINECODE45e6097c

也就是说，元素值与其索引的差值应该始终为 1。

一旦某个数字 INLINECODEde42ef73 缺失了，那么从 INLINECODEbacb0944 开始，后面的所有元素都会向前移动一位。这导致从缺失点开始，元素值与其索引的差值会变成 2。

我们可以得出结论：

  • 从左向右遍历数组。
  • 检查 arr[i] - i 的值。
  • 第一个使得 INLINECODE2e6206f4 的位置 INLINECODE47895d3c，说明缺失的数字就是 i + 1（即索引加1）。

#### 复杂度分析

  • 时间复杂度：O(n)。虽然还是线性的，但相比双重循环，常数项大大减小了。我们只遍历了一次数组。
  • 空间复杂度：O(1)。

#### 代码示例（C++）

#include 
#include 
using namespace std;

int missingNumber(vector& arr) {
    int n = arr.size() + 1;
    
    for(int i = 0; i < n - 1; i++) {
        // 检查：元素值 是否等于 (索引 + 1)
        // 如果不相等，说明本该在这个位置上的数字 (i + 1) 缺失了
        if(arr[i] != i + 1) {
            return i + 1;
        }
    }
    
    // 如果循环结束都没返回，说明是最后一个数字 n 缺失了
    return n;
}

int main() {
    vector arr = {1, 2, 3, 4, 6, 7, 8};
    cout << "缺失的数字是: " << missingNumber(arr) << endl; // 输出 5
    return 0;
}

方法三：更优方法 2 – 数学公式法（求和法）

如果不考虑数组的“有序”特性，单从“1 到 n 的自然数”这个条件出发，我们可以利用数学公式来解决这个问题。

#### 核心思路

我们知道 INLINECODEa27b99ed 到 INLINECODEc13d4c17 的求和公式是：

$$ S_n = \frac{n \times (n + 1)}{2} $$

现在数组中少了一个数，我们只需要：

  • 计算出原本应有的总和 INLINECODE7528d36c（即 INLINECODEfa857381 到 n 的和）。
  • 计算当前数组中所有元素的实际总和 actual_sum。
  • 两者相减：missing_number = expected_sum - actual_sum。

#### 注意事项（溢出风险）

这是一个非常经典的面试陷阱。当 INLINECODEbb0fcd9e 很大时（例如接近 INLINECODEc1287ce5），n * (n + 1) 的结果可能会超过整数类型的最大值，导致溢出。

解决方案：为了避免溢出，我们可以不直接算出 INLINECODEc10c8d84，而是在遍历数组时进行减法操作。或者使用更大的数据类型（如 INLINECODE6c8e7237 或 BigInteger）来存储总和。

#### 代码示例（Java 处理溢出）

class MissingNumberSum {
    static int missingNumber(int[] arr) {
        int n = arr.length + 1;
        
        // 使用 long 类型防止计算总和时溢出
        long expectedSum = (long) n * (n + 1) / 2;
        
        long actualSum = 0;
        for (int num : arr) {
            actualSum += num;
        }
        
        return (int)(expectedSum - actualSum);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 8, 9};
        System.out.println("缺失的数字是: " + missingNumber(arr)); // 输出 7
    }
}

方法四：期望的高效方法 – 二分查找

终于，我们要用上“有序数组”这个最强大的武器了。利用二分查找，我们可以将时间复杂度降低到 O(log n)。

#### 核心思路

基于我们在“方法二”中发现的规律：

  • 如果在 INLINECODEc69bbbad 位置之前的元素都没有缺失，那么 INLINECODEba63fe1d 应该等于 mid + 1。

* 即 arr[mid] - mid == 1。

* 这说明缺失的数字在右半部分（high 区域）。

  • 如果在 INLINECODE9f6cc038 位置之前已经发生了缺失，那么 INLINECODE53ccfd7b 应该大于 mid + 1。

* 即 arr[mid] - mid > 1。

* 这说明缺失的数字在左半部分（low 区域，包括 mid）。

通过不断缩小搜索范围，最终 INLINECODE27662a5b 会指向第一个不满足 INLINECODE2342c24d 的位置，即缺失数字的索引。

#### 算法步骤

  • 初始化 INLINECODE1ec17bad, INLINECODE69fe5001 (数组的最后一个索引)。
  • 进行循环，条件是 INLINECODE6fbc3eb7（确保区间内至少有两个元素可供比较，或者使用标准 INLINECODE9201da86 写法）。
  • 计算 mid = low + (high - low) / 2。
  • 如果 INLINECODE329b4225：说明左边没有缺失，向右找，INLINECODEe1b9e789。
  • 如果 INLINECODE5def2b0b：说明左边已经发生了缺失，向左找，INLINECODE8335915e。
  • 最后，INLINECODE8bb462de 或者 INLINECODEb5b15bd2 往往就是答案，具体根据循环结束条件而定。对于 INLINECODEecd3b027 到 INLINECODEdd2c3487 的问题，答案通常可以直接通过 INLINECODEab619cf8 或 INLINECODE54cee2a1 推导。最稳妥的方式是最后检查一下 INLINECODEae3491e8 和 INLINECODE863ce2bc。

#### 复杂度分析

  • 时间复杂度：O(log n)。每次循环都将搜索范围减半。
  • 空间复杂度：O(1)。

#### 代码实现（Python）

def missing_number_binary_search(arr):
    n = len(arr) + 1
    low, high = 0, len(arr) - 1

    # 标准二分查找框架
    while low <= high:
        mid = low + (high - low) // 2
        
        # 如果元素值等于索引+1，说明左边没问题，缺失的在右边
        if arr[mid] == mid + 1:
            low = mid + 1
        else:
            # 否则，缺失的在左边（或者就是 mid 位置对应的数缺失了）
            high = mid - 1
            
    # 循环结束时，low 指向了第一个“值与索引不匹配”的位置
    # 因为 arr[i] 本该是 i+1，所以缺失的数就是 low + 1
    return low + 1

if __name__ == "__main__":
    # 示例 1
    arr1 = [1, 2, 3, 4, 6, 7, 8]
    print(f"数组 {arr1} 中缺失的数字是: {missing_number_binary_search(arr1)}") # 输出 5

    # 示例 2：缺失的是第一个数字
    arr2 = [2, 3, 4, 5]
    print(f"数组 {arr2} 中缺失的数字是: {missing_number_binary_search(arr2)}") # 输出 1

常见陷阱与最佳实践

在实际开发或面试中，处理这个问题时你可能会遇到以下坑点：

  • 整型溢出：在使用求和公式时，务必注意大数相乘的溢出问题。这是面试官最常问的 follow-up 问题。使用位运算、循环减法或者更大的数据类型是标准解法。
  • 边界条件：

* 如果缺失的是 INLINECODE34911ec3：二分查找的逻辑必须能处理 INLINECODE144ddeb2 的情况。

* 如果缺失的是 n：很多简单的循环法需要单独处理这种情况，因为循环结束时可能还没返回。

  • 算法选择：

* 如果数组很小，线性扫描（方法二）实际上可能比二分查找更快，因为没有递归或复杂的循环开销，且对 CPU 缓存更友好。

* 如果数组非常大（例如数百万个元素），二分查找（方法四）的优势就非常明显了。

总结

在这篇文章中，我们一起探讨了四种在有序数组中查找缺失自然数的方法。从最朴素的 O(n²) 搜索，到利用索引特性的 O(n) 扫描，再到数学求和法，最后达到了 O(log n) 的二分查找最优解。

核心要点回顾：

  • 利用有序性：只要看到“有序”，第一时间想二分查找。
  • 观察规律：INLINECODEfcf5d6a7 与 INLINECODE2abe8d61 的关系（arr[i] == i + 1）是解决这个问题的数学本质。
  • 注意细节：处理大数求和时防止溢出。

希望这些分析能帮助你在下次遇到类似问题时，能够游刃有余地选择最优解法！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/33631.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年