重生之我是孔乙己——查找数组缺失元素的几种方法-Toy模板网

这篇具有很好参考价值的文章主要介绍了重生之我是孔乙己——查找数组缺失元素的几种方法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

重生之我是孔乙己——查找数组缺失元素的几种方法

💌 博客内容：查找缺失元素

😀 作者：陈大大陈

🚀 个人简介：一个正在努力学技术的准前端，专注基础和实战分享，欢迎私信！

💖 欢迎大家：这里是CSDN，我总结知识和写笔记的地方，喜欢的话请三连，有问题请私信 😘 😘 😘

题目

排序法

异或法

最天才的方法

题目

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

示例 1：

输入：[3,0,1]
输出：2

示例 2：

输入：[9,6,4,2,3,5,7,0,1]
输出：8

排序法

第一种方法，需要用到qsort函数，先将数组按从小到大排好序，然后遍历，当下标与该数组元素不相等时，返回这个数组元素的值。

冒泡排序的时间复杂度是o(n^2)，而快速排序的时间复杂度是o(n*logn)，我们选择效率更优的快速排序。排序之后我们需要遍历数组，那程序总共需要执行n*logn+n次。

时间复杂度是o(n*logn)。

#include<stdio.h>
#include<stdlib.h>
int cmp(const void* a, const void* b)
{
	return *(int*)a - *(int*)b; //由小到大排序
	//return *(int *)b - *(int *)a; 由大到小排序
}
int missingNumber(int* nums, int NumsSize)
{
	int i;
	qsort(nums, NumsSize, sizeof(nums[0]), cmp);
	for (i = 0; i <=NumsSize; i++)
	{
		if (i != nums[i])
		{
			return i;
		}
	}
	return -1;
}
int main()
{
	int a[] = {7,9,10 ,0,3,4,1,2,5,6};
	if (missingNumber(a, sizeof(a) / sizeof(a[0])) == -1)
	{
		printf("未找到\n");
	}
	else
		printf("%d",missingNumber(a, sizeof(a) / sizeof(a[0])));
	return 0;
}

异或法

异或，这个方法思路类似于之前找单身狗那道题，异或的两个元素相同为0，相异为1。

要注意第二次遍历次数是数组大小加一，原因是要加上缺失的那一个元素。

除了缺失的元素，其余元素异或的结果一定为0，所以第二次异或的结果一定是缺失的元素值。

程序要执行2n次。

时间复杂度：o(n)，比第一种效率更高。

#include<stdio.h>
#include<string.h>
int main()
{
	int a[] = { 7,9,10 ,0,3,4,1,2,5,6 };
	int i = 0;
	int x = 0;
	while (i <sizeof(a)/sizeof(a[0]))
	{
		x ^= a[i];
		i++;
	}
	for (i = 1; i <= sizeof(a)/sizeof(a[0]) + 1; i++)
	{
		x ^= i;
	}
	printf("%d", x);
	return 0;
}

最天才的方法

鬼才才能想出来的方法，果然是大道至简！

第一次遍历将整个数组以及缺失的元素加到一起。

第二次遍历将原数组的值挨个减掉，这样最后剩下的值一定就是所缺失的元素。

时间复杂度是惊人的o(n),芜湖，最好使竟是最单纯的，感动了！

重生之我是孔乙己——查找数组缺失元素的几种方法

int missingNumber(int* nums, int numsSize) {

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

}

总结
感谢观看，本文到这里就结束了，如果觉得有帮助，请给文章点个赞吧，让更多的人看到。🌹 🌹 🌹