?

• ?? 博客內(nèi)容：查找缺失元素

• ?? 作??者：陳大大陳

• ?? 個人簡介：一個正在努力學(xué)技術(shù)的準前端，專注基礎(chǔ)和實戰(zhàn)分享 ，歡迎私信！

• ?? 歡迎大家：這里是CSDN，我總結(jié)知識和寫筆記的地方，喜歡的話請三連，有問題請私信 ?? ?? ??

目錄

題目?

排序法?

異或法?

最天才的方法

題目?

數(shù)組nums包含從0到n的所有整數(shù)，但其中缺了一個。請編寫代碼找出那個缺失的整數(shù)。你有辦法在O(n)時間內(nèi)完成嗎？?

示例 1：

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

示例 2：

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

排序法?

第一種方法，需要用到qsort函數(shù)，先將數(shù)組按從小到大排好序，然后遍歷，當(dāng)下標與該數(shù)組元素不相等時，返回這個數(shù)組元素的值。?

冒泡排序的時間復(fù)雜度是o(n^2)，而快速排序的時間復(fù)雜度是o(n*logn)，我們選擇效率更優(yōu)的快速排序。?排序之后我們需要遍歷數(shù)組，那程序總共需要執(zhí)行n*logn+n次。

時間復(fù)雜度是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。?

要注意第二次遍歷次數(shù)是數(shù)組大小加一，原因是要加上缺失的那一個元素。

除了缺失的元素，其余元素異或的結(jié)果一定為0，所以第二次異或的結(jié)果一定是缺失的元素值。

程序要執(zhí)行2n次。?

時間復(fù)雜度：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;
}

最天才的方法

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

第一次遍歷將整個數(shù)組以及缺失的元素加到一起。

第二次遍歷將原數(shù)組的值挨個減掉，這樣最后剩下的值一定就是所缺失的元素。

時間復(fù)雜度是驚人的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;

}

總結(jié)
??感謝觀看，本文到這里就結(jié)束了，如果覺得有幫助，請給文章點個贊吧，讓更多的人看到。?? ?? ??

?

??也歡迎你，關(guān)注我。?? ?? ??

??原創(chuàng)不易，還希望各位大佬支持一下，你們的點贊、收藏和留言對我真的很重要?。。?? ?? ?? 最后，本文仍有許多不足之處，歡迎各位認真讀完文章的小伙伴們隨時私信交流、批評指正！下期再見。??文章來源地址http://www.zghlxwxcb.cn/news/detail-409520.html

到了這里，關(guān)于重生之我是孔乙己——查找數(shù)組缺失元素的幾種方法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！