C++实现LeetCode缺失数字问题的存储与识别逻辑疑问

核心疑问解答 #

1. 遍历过的数字信息存在哪里？ #

存在代码里的temp辅助数组中，这个数组专门用来标记哪些数字已经在原数组中出现过。

2. 如何识别存在的数字和缺失的数字？ #

• 存在的数字：遍历原数组时，把temp数组对应位置的值设为1，以此标记该数字已经出现。
• 缺失的数字：最后遍历temp数组，找到值为0的位置，这个位置对应的数字就是缺失的。

3. 判断缺失数字的核心逻辑 #

这道题的隐含条件是：原数组包含1~N+1中的N个数字（原数组长度为N，恰好缺失1个）。所以我们创建长度为N+1的temp数组，每个位置对应1~N+1中的一个数字，通过标记已出现的数字，最后未被标记的位置就对应缺失的数字。

逐行代码解析 #

完整代码如下：

void findMissing(int arr[], int N)
{
    int i; // 用作循环遍历的变量
    int temp[N + 1]; // 辅助标记数组，长度N+1对应1~N+1的所有可能数字
    for(int i = 0; i <= N; i++){ // 初始化temp数组所有元素为0，代表所有数字初始状态是「未出现」
      temp[i] = 0;
    }
   
    for(i = 0; i < N; i++){ // 遍历原数组的每一个数字
      temp[arr[i] - 1] = 1; // 把对应数字的标记位设为1：比如数字1对应temp[0]，数字7对应temp[6]，标记为1表示这个数字已出现
    }
 
    int ans;
    for (i = 0; i <= N ; i++) { // 遍历辅助数组找未标记的位置
        if (temp[i] == 0) // 找到值为0的位置，说明对应的数字没在原数组中出现过
            ans = i  + 1; // 位置i对应数字i+1，比如位置3对应数字4
    }
    std::cout << ans; // 输出找到的缺失数字
}
 
/* Driver code */
int main()
{
    int arr[] = { 1, 3, 7, 5, 6, 2 }; // 测试用数组，长度6，对应1~7中缺失一个数字
    int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度：总字节数除以单个元素的字节数，得到n=6
    findMissing(arr, n); // 调用查找缺失数字的函数
}

实际执行流程示例（以测试数组为例） #

测试数组是{1,3,7,5,6,2}，长度n=6：

1. 初始化temp数组长度为7（6+1），所有元素初始值都是[0,0,0,0,0,0,0]
2. 遍历原数组，逐个标记已出现的数字：
   • 数字1 → temp[0] = 1 → temp变为[1,0,0,0,0,0,0]
   • 数字3 → temp[2] =1 → temp变为[1,0,1,0,0,0,0]
   • 数字7 → temp[6] =1 → temp变为[1,0,1,0,0,0,1]
   • 数字5 → temp[4] =1 → temp变为[1,0,1,0,1,0,1]
   • 数字6 → temp[5] =1 → temp变为[1,0,1,0,1,1,1]
   • 数字2 → temp[1] =1 → temp变为[1,1,1,0,1,1,1]
3. 遍历temp数组，发现temp[3] =0，对应数字是3+1=4，这就是缺失的数字，最后输出4。

内容的提问来源于stack exchange，提问作者anon