【leetcode】消失的数字-Toy模板网

这篇具有很好参考价值的文章主要介绍了【leetcode】消失的数字。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

大家好，我是苏貝，本篇博客带大家刷题，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️

点击查看题目

【leetcode】消失的数字,leetcode,leetcode,算法,职场和发展

1.暴力求解法

通过2个for循环，遍历查找0-n中缺少的数字，比较简单，不写，时间复杂度为O(N^2)

2.采用异或的方法（同单身狗问题）

点击去了解异或，位置在④.3
异或：两个整数的相同位置：相同为0，不同为1（二进制），易知a^ a=0，a^ 0=a；具有交换律，所以a^ b^ a=a^ a^ b=0^b=b。
在本题中，先使x=0（因为0^ 任何数=任何数本身），再让x与0-n（n是数组的元素个数）的所有数字异或，再让x与nums数组的全部元素异或；当数组为[3,0,1]时，x与0-3的全部数字异或，再与数组元素[3,0,1]异或，即
【leetcode】消失的数字,leetcode,leetcode,算法,职场和发展
这样就能得出消失的数字，执行次数为2n+1，时间复杂度为O(N)，代码为：

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

3.先求和再减去数组元素

先求出0-n（n是数组的元素个数）所有数字之和，再减去数组nums中的所有元素，得到的自然是消失的数字。如当数组为[3,2,0,1]时，求出0-4所有数的和=10，再-0-1-2-3=4，所以消失的数字是4。
时间复杂度为O(N)，代码为：

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