面试题 消失的两个数字.pdf

### 知识点详解 #### 标题与描述解析 - **标题**：“面试题 消失的两个数字.pdf” - **描述**：“面试题 消失的两个数字” 此面试题要求找到一个包含从1到N所有整数的数组中缺失的两个数字。根据描述，我们可以了解到该题目是“消失的数字”问题的一种变体，原问题可以在力扣（LeetCode）上找到。本题要求在O(N)的时间复杂度和O(1)的空间复杂度下完成。 #### 问题背景 - **来源**：力扣（LeetCode），题目编号为17.19。 - **相关联题目**：面试题 17.04. 消失的数字 - 力扣（LeetCode）。 - **参考材料**：鹏哥C语言、航哥数据结构。 #### 问题描述 - **目标**：给定一个包含从1到N所有整数但缺失了两个数字的数组，要求找到这两个缺失的数字。 - **约束条件**： - 数组长度为N-2。 - 要求时间复杂度为O(N)。 - 要求空间复杂度为O(1)。 - **示例**： - 示例1：输入: [1] 输出: [2,3] - 示例2：输入: [2,3] 输出: [1,4] #### 分析与解答思路 ### 方法一：纯暴力法 - **核心思想**：创建一个大小为N的辅助数组，用来标记数组中的每个元素是否出现过。 - **步骤**： 1. 创建一个大小为30000的int类型的数组`arr`（考虑最坏情况下的数组长度）。 2. 使用循环遍历给定数组，对于每个元素`nums[i]`，在`arr[nums[i]]`位置设置标记。 3. 再次遍历`arr`，找出没有被标记的位置，这些位置即为缺失的数字。 - **关键点**： - 需要注意题目要求的空间复杂度为O(1)，而此处使用了一个额外的数组，实际不符合要求。 - 实际上，这种方法的空间复杂度为O(N)。 - **代码实现**： ```c int* missingTwo(int* nums, int numsSize, int* returnSize){ int i; *returnSize = 2; int *result = (int *)malloc(2 * sizeof(int)); int arr[30000] = {0}; for (i = 0; i < numsSize; i++){ arr[*(nums + i)]++; } int count = 0; for (i = 1; i <= numsSize + 2; i++){ if (arr[i] == 0){ result[count++] = i; } } return result; } ``` ### 方法二：位运算异或法 - **核心思想**：利用异或运算的性质来解决问题。 - **步骤**： 1. 计算1到N的所有整数的异或结果。 2. 计算给定数组中所有元素的异或结果。 3. 对步骤1和步骤2的结果进行异或操作，得到的结果是由缺失的两个数字异或得到的。 4. 由于缺失的是两个数字，我们可以利用异或结果中任意一个不为0的位作为分界线，将所有的数字分为两组，并对每组分别进行异或操作，最终得到两个缺失的数字。 - **关键点**： - 异或运算满足交换律和结合律。 - 相同数字异或结果为0。 - **代码实现**： ```c int* missingTwo(int* nums, int numsSize, int* returnSize){ int i; *returnSize = 2; int *result = (int *)malloc(2 * sizeof(int)); int x1 = 0, x2 = 0, index = 0, i; for (i = 1; i <= numsSize + 2; i++){ x1 ^= i; } for (i = 0; i < numsSize; i++){ x1 ^= *(nums + i); } // 寻找x1中第一个非0位 for (i = 0; i < 32; i++){ if ((x1 & (1 << i)) != 0){ index = i; break; } } for (i = 1; i <= numsSize + 2; i++){ if ((i & (1 << index)) != 0) x2 ^= i; } for (i = 0; i < numsSize; i++){ if (((*(nums + i)) & (1 << index)) != 0) x2 ^= *(nums + i); } result[0] = x1; result[1] = x2; return result; } ``` ### 总结 - **方法一**：虽然直观易理解，但是其空间复杂度为O(N)，不符合题目要求。 - **方法二**：充分利用了异或运算的特点，既满足了时间复杂度的要求，又达到了空间复杂度的要求，是更优解。 - **注意事项**： - 确保正确理解和应用位运算，特别是异或运算。 - 使用动态内存分配时，别忘了释放内存。 - 在编写代码时，注意边界条件的处理。