消失的数字

消失的数字

找出0--N数字中消失的数字，程序时间复杂度为O(n).

例

输入：1 0 2 4 5
输出: 3

方法一

直接求和然后相减

int main()
{
	int n = 0;
	int arr1[100] = { 0 };
	int sum1 = 0;
	int sum2 = 0;
	printf("请输入N: ");
	scanf("%d", &n);
	int i = 0;
	printf("请输入你的数: ");
	for (i = 0; i < n; i++)
	{
		scanf("%d", &arr1[i]);
	}
	printf("你的数组为: ");
	for (i = 0; i < n; i++)
	{
		printf("%d ", arr1[i]);
		sum1 += arr1[i];
	}
	printf("n");
	for (i = 0; i < n + 1; i++)
	{
		sum2 += i;
	}
	printf("消失的数为: %d", sum2 - sum1);

	return 0;
}

结果运行

 方法二

采用异或的方法，因为异或相同位为0，不同位1，用0--n与数组比较，相同则为0，不同则为消失的数

先将ret = 0   与0---n异或                        这里n为5

ret = 0^1^2^3^4^5

在与数组中其他数异或                        输入的数据为 1 0 2 4 5

ret = 0^1^2^3^4^5^1^0^2^4^5

ret = 3

int main()
{
	int n = 0;
	int arr1[100] = { 0 };
	int ret = 0;
	printf("请输入N: ");
	scanf("%d", &n);
	int i = 0;
	printf("请输入你的数: ");
	for (i = 0; i < n; i++)
	{
		scanf("%d", &arr1[i]);
	}
	printf("你的数组为: ");
	for (i = 0; i < n; i++)
	{
		printf("%d ", arr1[i]);
	}
	for (i = 0; i < n+1 ; i++)
	{
		ret ^= i;
		
	}
	printf("n");
	for (i = 0; i < n; i++)
	{
		ret ^= arr1[i];

	}
	printf("消失的数为: %d", ret);
	return 0;
}