leetcode：面试题 17.04. 消失的数字（找单身狗/排序/公式）

一、题目：

函数原型：int missingNumber(int* nums, int numsSize)

二、思路：

思路1

利用“找单身狗”的思路（n^n=0；0^n=n），数组中有0-n的数字，但缺失了一个数字x。将这些数字按位异或0-n所有数字，那么最后的结果为0^x，最终结果就是x。

思路2

先将数组排序（升序），遍历数组，如果前一元素+1 不等于 后一元素，则说明缺失的元素是前一元素+1。但是如果缺失的是0或者n，无法用上述方法解决，需要先判断排序后的首元素和尾元素是否等于0、n；如果不等于，确实的元素就是0或n。

 

思路3

等差数列求和，求0 ~（numsSize+1）的和，再减去数组的所有元素和，差值即为缺失的数字。

三、代码：

代码1

int missingNumber(int* nums, int numsSize)
{int result = 0;for (int i = 0; i < numsSize; i++)//按位与数组中所有数字{result ^= nums[i];}for (int i = 0; i <= numsSize; i++)//按位与0-n所有数字{result ^= i;}return result;
}

代码2

int cmp(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}int missingNumber(int* nums, int numsSize)
{qsort(nums, numsSize, sizeof(int), cmp);if (nums[0] != 0)return 0;else if (nums[numsSize - 1] != numsSize)return numsSize;else{int i = 0;for (i = 0; i < numsSize - 1; i++){if ((nums[i] + 1) != nums[i + 1])return nums[i] + 1;}}
}

代码3

int missingNumber(int* nums, int numsSize)
{int sum = (0 + numsSize) * (numsSize + 1) / 2;for (int i = 0; i < numsSize; i++){sum -= nums[i];}return sum;
}