【LeetCode每日一题——消失的数字】

消失的数字

面试题 17.04. 消失的数字

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

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

思路一：开辟一个新数组，将新数组下标为nums[ i ]的元素赋值为-1；再遍历新数组，将新数组中不为-1的下标返回。

时间复杂度：O(N)
空间复杂度：O(N)

/*思路一*/intmissingNumber(int* nums,int numsSize){int* num =(int*)malloc(sizeof(int)*(numsSize +1));int i =0;for(i =0; i < numsSize; i++){*(num+nums[i])=-1;}for(i =0; i < numsSize +1; i++){if(num[i]!=-1){break;}}return i;}

思路二：亦或；定义x=0；x跟数组中的元素都亦或一遍，然后再和0~N之间的数字亦或一遍，x就是缺失的数字。（亦或有交换律，其他数字出现2次，只有缺失的那个数字出现1次）

时间复杂度：O(N)
空间复杂度：O(1)

/*思路二*/intmissingNumber(int* nums,int numsSize){int x=0;int i=0;for(i=0;i<numsSize;i++){
        x^=nums[i];}for(i=0;i<=numsSize;i++){
        x^=i;}return x;}

0和任何值的异或等于本身，即：A ^ 0 = A
异或本身等于0，即 A ^ A = 0
异或满足结合律，即 A ^ B ^ C = A ^ ( B ^ C)

思路三：求和；求出前n+1个数字之和，在减去数组中的数字，就是消失的数字。
时间复杂度：O(N)
空间复杂度：O(1)

/*思路三*/intmissingNumber(int* nums,int numsSize){int i=0;int sum=0;for(i=0;i<=numsSize;i++){
        sum+=i;}for(i=0;i<numsSize;i++){
        sum-=nums[i];}return sum;}