当前位置：首页 > news >正文

数据结构 ——— 数组 nums 包含了从 0 到 n 的所有整数，但是其中缺失了一个，请编写代码找出缺失的整数，并且在O(N)时间内完成

news 2024/11/14 8:23:20

题目要求

代码实现

方法1（异或法）：

异或算法的时间复杂度：

方法2（等差数列公式）：

等差数列公式的时间复杂度：

题目要求

整型数组 nums 包含了从 0 到 n 的所有整数，但是其中缺失了一个，编写一个 missingNumber 函数，找出缺失的整数，并且将 missingNumber 函数的时间复杂度控制在 O(N) 内完成‘

nums 为：整型数组首元素地址

numsSize 为：nums 数组的元素个数

代码实现

方法1（异或法）：

代码演示：

int missingNumber(int* nums, int numsSize)
{int x = 0;// 循环1for (int i = 0; i < numsSize; i++){x = x ^ nums[i];}// 循环2for (int i = 0; i < numsSize + 1; i++){x = x ^ i;}return x;
}

代码解析：

0 异或任何整数，结果为任何整数

0 ^ x = x

两个相同的整数异或，结果为0

a ^ a = 0

两个相同的整数异或再异或一个其他的整数，结果为其他的整数，且异或满足交换律

a ^ a ^ b = b <===> a ^ b ^ a = b

由以上的结论推导出代码的含义：

创建整型变量 x 并赋值为 0 ，因为 0 异或任何整数，结果为任何整数，所以再使用 x 异或 nums 数组中的所有整数，再利用 numsSize 遍历完整的 nums 数组，再和 x 异或，异或完之后的 x 就是缺失的那个值

举例说明：

nums 的元素为：[0, 1, 2, 3, 5]

x 为：0

循环1 为：0 ^ 1 ^ 2 ^ 3 ^ 5

循环2 为：0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5

由以上的代码得：

0 ^ 0 ^ 1 ^ 2 ^ 3 ^ 5 ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5

= 0 ^ 0 ^ 0 ^ 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 3 ^ 5 ^ 5 ^ 4

= 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 4

= 4

代码验证：

异或算法的时间复杂度：

循环1 执行了 N 次，循环2 执行了 N+1 次

得出算法的时间复杂度函数式：

时间复杂度函数式：F(N) = N + N + 1 = 2 * N + 1

根据时间复杂度函数式和大O的渐进表示法规则得出：只保留最高项（去掉 1）；如果最高阶项存在且不是1，则去除与这个项目相乘的常数（除去 F(N) 中的2 ），得出大O的渐进表示法：

大O渐进表示法：O(N)

方法2（等差数列公式）：

代码演示：

int missingNumber(int* nums, int numsSize)
{// 首项加尾项乘以项数除以2int x = (0 + numsSize) * (numsSize + 1) / 2;// 循环1for (int i = 0; i < numsSize; i++){x = x - nums[i];}return x;
}

代码解析：

首项加尾项乘以项数除以2，根据这个公式就能求出完整的 nums 数组的所有数的和并存储到整型变量 x 中

最后再利用循环1 遍历 nums 数组的中数，并用 x 依次递减，最后 x 的值就是 nums 数组缺失的数

代码验证：