方法1：暴力解法
直接用for循环从0~N遍历，若不存在返回对应数字即可。
时间复杂度O（N^2）。
空间复杂度O（1）。
int missingNumber(int* nums, int numsSize) { // i 是要找的数字 ，j是遍历数组的下标 int i = 0; for (i = 0; i < numsSize; i++) { int j = 0; for (j = 0; j < numsSize; j++) { //数组中存在 数字i，跳出循环，否则return i if (i == nums[j]) { break; } } //遍历到最后，说明没找到 if(j==numsSize) { return i; } } //只有一个元素0时，返回1 return i; }
方法2：哈希
利用hash数组记录出现的数字，如果出现过对应hash为1.
再次遍历hash数组，数组值为0，就是未出现的元素。
时间复杂度O（n）
空间复杂度O（n）
int missingNumber(int* nums, int numsSize) { //申请一个大小为(numsSize+1)的数组,注意要多申请一个！ int * hash =(int *)malloc(sizeof(int)*(numsSize+1)); //申请完别忘记初始化 memset(hash,0,sizeof(int)*(numsSize+1)); int i = 0; for (i = 0; i < numsSize; i++) { //用hash记录nums中元素是否出现过 hash[nums[i]] = 1; } for (i = 0; i < numsSize; i++) { if (hash[i] == 0) { return i; } } return i; }
方法3：异或
先将数组中所有元素异或，然后再与0~n异或，最后得到的数字即为所求数字。（此方法需要明白异或的性质：相同异或为0，相异异或为1）
时间复杂度O（n）
空间复杂度O（1）
int missingNumber(int* nums, int numsSize) { int ret = 0; //先与数组中的元素异或 for (int i = 0; i < numsSize; i++) { ret ^= nums[i]; } //再与0~N的元素异或 for (int i = 0; i < numsSize+1; i++) { ret ^= i; } return ret; }
以上是本人对此题的见解，如果大佬们有什么意见，欢迎在评论区里讨论💞
