面试题:消失的数字
数组nums包含从0到n的所有整数,但是其中缺了一个,请编写代码找出那个缺失的整数,你有办法O(N)时间内完成吗?
方法1.排序:依次查找
如果下一个数不是上一个数+1,那么上一个数字+1就是消失的数字
冒泡排序的话时间复杂度是O(n^2)
qsort排序的话是O(NlogN)
需要用一个循环来判断如果下一个数不是上一个数+1,那么上一个数字+1就是消失的数字,准确地来说时间复杂度是O(NlogN+N),最后的N可以忽略掉,所以时间复杂度是O(N*logN).
时间复杂度都不满足题目的要求,所以这道题目不能使用排序
方法2.异或:相异为1,相同为0
思路分析
用一个数字x跟0~n的数字异或,再和缺失数字的数组异或
异或的特点:
参与运算的两个值,如果两个值相同,则结果为1,不同为1
(1)0 ^ 0=0 0 ^ 1=1
0和任何数异或=任何数
(2)1^0=1 1 ^1=0
1异或任何数=任何数取反
(3)任何数异或自己相当于把自己本身置0
题目分析:
1.将x置为0,让它去异或现有的缺失数字的数组里面的各个数字,结果保存到x中
2.再用上一步得到的x去异或原本完整的数组里面的各个元素,根据异或的特点,相同的两个数之间异或结果为0,那么最终两个数组相同的数字异或完之后剩下0去异或原来完整的数组中没有匹配到的数字(也就是消失的数字),结果就是消失的数字
画图讲解:
0 1 2 3 4 5 6 7 8 9
假设x就是消失的数字
假设x=0
0和任何数字异或,结果是任何数
先和第一个缺失数字的数组异或,遍历数组的时间复杂度是O(N)
再和第二个完整的数组异或,时间复杂度是O(N+1)
总的来说这个方法的时间复杂度是O(N+N+1)也就是O(2*N+1)
时间复杂度实际上还是O(N)
注意:
异或满足交换律
1 1 2异或和1 2 1 异或的结果相同
int missingNumber(int* nums, int numsSize) { int x = 0; //和数组里面的每个值异或 for (int i = 0; i < numsSize; ++i) { x ^= nums[i]; } for (int i = 0; i < numsSize; i++) { x ^= i; } return x; }
方法3.0-N等差数列计算完整数组的和,减去缺失数字的数组里面的各个数字
等差数列求和的时间复杂度是O(1)
减数组里面的值需要遍历一遍,时间复杂度是O(N)
这个方法的时间复杂度是O(N+1)也就是O(N)
#include<stddef.h> //size_t是C标准在stddef.h中定义的,size_t类型表示C中任何对象所能达到的最大长度,它是无符号整数 //size_t在32位系统上定义为unsigned int,也就是32位无符号整型. //size_t在64位系统上定义为unsigned int,也就是64位无符号整型. int missingNumber(int* nums, int numsSize) { int x = (0 + numsSize) * (numsSize+1) / 2; for (size_t i = 0; i < numsSize; i++) { x -= nums[i]; } return x; }
