面试题 17.04. 消失的数字

一、题目描述

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

二、示例

输入：[3,0,1]
输出：2

输入：[9,6,4,2,3,5,7,0,1]
输出：8

三、实现

方法1 排序后顺序查找

排序，依次查找，如果下一个数不是上一个数加1，则上一个数加1就是消失的数字。

int missingNumber(int* nums, int numsSize) {// sortfor (int i = numsSize; i > 0; --i) {int exchange = 0;for (int j = 1; j < i; ++j) {if (nums[j - 1] > nums[j]) {int tmp = nums[j - 1];nums[j - 1] = nums[j];nums[j] = tmp;exchange = 1;}}if (exchange == 0) {break;}}// searchfor (int i = 0; i < numsSize - 1; ++i) {if (nums[i] + 1 != nums[i + 1]) {return nums[i] + 1;}}return -1;
}

这里的排序使用的是简单的冒泡排序时间复杂度O(n²)，遍历数组时间复杂度为O(n)，总体时间复杂度为O(n²)，即便使用更为高效的排序算法，总体时间复杂度不是O(n)。

方法2 利用异或性质

两个相同的数异或为0：x ^ x = 0
并且异或满足交换律：a ^ b ^ c = a ^ c ^ b

让数组的size个数与[0, size-1]共size个数异或，得到的结果再与size异或，最终得到的便是[0, size]中缺的那个整数。

int missingNumber(int* nums, int numsSize){int temp = 0;for(int i = 0; i < numsSize; ++i) {temp ^= i;temp ^= nums[i];}temp ^= numsSize;return temp;
}

方法3 利用求和

0-N等差数列公式计算求和结果，然后减数组中的所有元素。

int missingNumber(int* nums, int numsSize) {int sum = (1 + numsSize) * numsSize / 2;for (int i = 0; i < numsSize; ++i) {sum -= nums[i];}return sum;
}