C语言--经典面试题(2)：消失的数字

题目链接： 面试题 17.04. 消失的数字 - 力扣（LeetCode） (leetcode-cn.com)

这道题可以用三种思路来分析，其中第一种是不考虑时间复杂度的，也就是不满足题目要求的，纯属写着玩儿，感兴趣的可以看看，另外两种都可以当作做题的参考。

思路一：排序法(不考虑时间复杂度)

这种方法就相当于暴力一点，我们可以直接将数组内的内容进行排序，然后看后面的数是否比前面大1就可以了，具体代码如下：

排序方法一：冒泡排序

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>     //printf
void bubble_sort(int arr[], int sz)
//冒泡排序
{
	int i, j = 0;
	int tmp = 0;
	for (i = 0; i < sz; i++)
	{
		for (j = 0; j < sz - i-1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

int missing_num(int arr[], int sz)
//寻找消失的数字
{
	for (int i = 0; i < sz; i++)
	{
		if ((arr[i + 1] - arr[i]) != 1)
		{
			return arr[i] + 1;
			break;
		}
	}
}

int main()
{
	int arr[] = { 9,6,4,2,3,5,7,0,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//冒泡排序
	bubble_sort(arr, sz);
	//找出消失的数字
	int n = missing_num(arr, sz);
	printf("%d", n);

	return 0;
}

输出结果：

由于这种方法的时间复杂度为O(N^2),所以不满足题目要求。

---

排序方法二：qsort函数排序(感兴趣的可以看看)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>     //printf
#include<stdlib.h>    //qsort
int com_int(const void* a, const void* b)
{
	return *(int*)a - *(int*)b;
        //升序(从小到大)
}

int main()
{
	int arr[] = { 3,0,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//排序
	qsort(arr, sz, sizeof(int), com_int);
	for (int i = 0; i < sz; i++)
	{
		if ((arr[i + 1] - arr[i]) != 1)
		{
			printf("%d", arr[i] + 1);
			break;
		}
	}

	return 0;
}

输出结果：

---

思路二：总和相减法

这种方法的思路就是，比如说数组arr[]={0,1,2,3,5,6,7,8,9};,我们就可以把0到9这10个数加起来，令其结果为sum1，然后再把数组arr中的所有元素的值加起来，令其结果为sum2，然后再让sum1减去sum2，其结果就为我们要找的数字。所以我们要先找到原数组中的最大值max和最小值min，因为找出来之后我们要相加的数就是max到min之间的数(包括max和min)，这样我们计算出来的sum1的值才不会多或少。 这种方法就相对来说比较巧妙，不过也可以为我们以后刷题时提供一些其他的思路,具体代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>     //printf
int arr_sum2(int arr[], int sz)
//计算sum2
{
	int sum2 = 0;
	for (int i = 0; i < sz; i++)
	{
		sum2 += arr[i];;
	}
	return sum2;
}

int arr_sum1(int max, int min)
//计算sum1
{
	int sum1 = 0;
	for (int i = min; i <= max; i++)
	{
		sum1 += i;
	}
	return sum1;
}

int com_int(int arr[], int sz)
//寻找数组中的最大值和最小值
{
	int max = 0;
	int min = 100;
	for (int i = 0; i < sz; i++)
	{
		if (arr[i] > max)max = arr[i];
		if (arr[i] < min)min = arr[i];
	}
	//计算sum1
	int sum1 = arr_sum1(max, min);
	return sum1;
}

int main()
{
	int arr[] = { 9,6,4,2,3,5,8,0,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//数组内元素个数
	int sum1 = com_int(arr, sz);
	//找出最大值和最小值并计算sum1
	int sum2 = arr_sum2(arr, sz);
	//计算sum2
	int n = sum1 - sum2;
	//寻找消失的数字
	printf("%d", n);

	return 0;
}

输出结果：

---

思路三：按位异或(^)法

按位异或的介绍

按位异或，符号为^，意思是将两个二进制数进行比较，从第一位开始，若位数上的数字不同，则该位上的结果就为真(1),相同则为假(0)。 例如：

//^按位异或 
#include<stdio.h>
main()
{
	int a = 3;
	//a=00000000000000000000000000000011=3
	int b = 5;
	//b=00000000000000000000000000000101=5
	//^：按（二进制）位异或 
	int c = a ^ b;//不同则为真，相同则为假 
	//c=00000000000000000000000000000110=6
	printf("c=%d", c);
	//c=6
}

我们在使用这个操作符的时候，必须要注意其几个特点：

1.a^ a = 0；

任意两个相同的数字异或后都等于0

2.0 ^ a = a；

0异或上任意一个数字结果都是原来的那个数字。

3.a ^ a ^ b = b

---

解题思路

因此在做这道题目的时候，我们就可以用一个数x1，来存储arr数组中所有元素互相异或的值，然后再用x2，来存储0到N中的元素互相异或的值，再让x1异或上x2，最后得出的结果就是消失的那个数字：

代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>     //printf
int main()
{
	int arr[] = { 9,6,4,2,3,5,8,0,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//对于这道题来说，arr数组中有多少个元素，则数组内的最大值即为元素个数的值
	int x1 = 0;
	int x2 = 0;
	int i = sz;
        //此时i=9
	do
	{
		x1 ^= arr[i - 1];
		//将arr数组中所有元素异或的结果存储在x1中
		x2 ^= i;
		//将0到i互相异或的结果存储到x2中
	} 
	while (--i);
	printf("%d", x1 ^ x2);
	//输出消失的数字

	return 0;
}

输出结果：

---

这道题的介绍到这里就结束了，如果你觉得本篇文章对你多少有些帮助，可以点个赞或者收藏一波支持一下哦，欢迎各位大佬批评指正，咱们下次再见！