2.数据结构面试题--消失的数字

面试题:消失的数字

数组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;
}