面试题 17.04. 消失的数字

消失的数字

题目描述：

➡️ 挑战链接 ⬅️
分析：

方法一：
题目给了我们一个很重要的条件，一群[0,n]的所有整数，只少了一个；
那么完整的数据是不是就是：0，1，2，3，4，5，6，……,n
现在缺了一个，那么我们是不是可以利用原来完整的数据总和减去现在数组的总和是不是就是缺的那个数呢？
而刚好完整的数组是从0到n的等差数列，我们就可以利用等差数列求和公式将完整的数据之和求出来，然后在遍历一遍现在的数组就可以得到缺失的数组之和；
代码实现：

int missingNumber(int* nums, int numsSize){
          int oldSum=(numsSize+1)*numsSize/2;//求完整数据之和
          for(int i=0;i<numsSize;i++)
          {
              oldSum-=nums[i];//求缺失数组之和
          }
          return oldSum;
}

1
2
3
4
5
6
7
8
9

时间复杂度：O（N）
空间复杂度：O（1）

方法二：
首先还是题目给定的[0,n]区间下手，我们不是缺一个嘛，我们现在将完整的数组开辟出来，先全部初始化为-1，然后再从元素组将数据一个一个拷贝下来，放进完整的数组里面，当然我们不能乱发，每个元素都有自己对应的位置，不要乱放，比如缺失数组里面的3，就应该放在完整数组下标为3的位置；依次类推~
最后我们在遍历一遍完整的数组，如果我们发现了元素值等于-1，那么就可以直接返回改下标值，该下标值就是缺失的数字：
画图演示：

时间复杂度：O（N）
空间复杂度：O（1）

代码实现：

int missingNumber(int* nums, int numsSize){
             int len=numsSize+1;
             int tmp[len];
             memset(tmp,-1,sizeof(tmp));
             for(int i=0;i<numsSize;i++)
             tmp[nums[i]]=nums[i];
             int j=0;
             for(j=0;j<len;j++)
             if(tmp[j]<0)
             break;
             return j;
}
1
2
3
4
5
6
7
8
9
10
11
12

方法三：
由于只是缺失一个数字，那么我们可以把原数据和现在的数据放在一起吧：
比：
例子中的：
3，0，1
原数据：0，1，2，3
现在： 3，0，1
我们把连个数组合起来是不是会发现只有2出现了一次，其它数据都出现了2次，那么我们是不是可以考虑利用异或的性质来解决；

异或性质：
a^a=0;
0^a=a;
a^ b ^ c=a ^ c ^ b

同样的道理，我们只需要对这合并起来的数据进行不断异或，最终全部异或完毕异或出来的数据就是缺失的那个数据了；
代码实现：

int missingNumber(int* nums, int numsSize){
            int x=0;
            for(int i=0;i<=numsSize;i++)
            x^=i;
            for(int i=0;i<numsSize;i++)
            x^=nums[i];
            return x;
}
1
2
3
4
5
6
7
8

时间复杂度：O（N）
空间复杂度：O（1）