前言：

• 博主實力有限，博文有什么錯誤，望各位大佬，不吝賜教，非常感謝！

• 這是博主的新專欄《劍指offer》第一篇，希望各位大佬多多支持，感謝！

• 如果對按位與&，按位異或^ ,按位或|，&&且，||或，不是太明白的見我另外一篇博客：

題目

消失的數字

一個陣列中含有從0到20的所有數字，但是陣列中缺少了0到20中的一個數，請你找出這個消失的數字

高效方法一：雙目運算子按位異或^

補充

• 按位異或^ 的規則是：

exp:a^b

比較a與b中二進制補碼(!!!)中每位，相同那么新形成的二進制對應位為0，不相同的為1

exp:

a= 1;b= 3;

a的補碼：

00000000 00000000 00000000 00000001

b的補碼：

00000000 00000000 00000000 00000011

a^b后的新的二進制補碼是：

00000000 00000000 00000000 00000010

• **按位異或的一些規律：**(!!!)

• 0與任何數異或都是任何數

• **1^ 2 ^ 3 ^2 ^ 3 =1**

這是理解本題目的**關鍵點**

!!!

思路：

正是因為1 ^ 2 ^ 3 ^4 ^5 ^ 2 ^3 ^ 4^ 5=1

因此對于本題；將陣列中所有數全部 按位異或 ^到一起

x=arr[0]^ arr[1]^ arr[2]^ … arr[19]

之后再將0到20的數字異或到一起

那么最后,x必然是那個消失的數

畢竟0到20重復的數都^沒了

代碼

int main()
{
	int x = 0;//用于存放按位異或的資料
	int arr[] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,20 };
	int sz = sizeof(arr) / sizeof(*arr);
	for (int i = 0; i < sz; i++)
	{
		x ^= arr[i];
	}
	//x=0^1^2^3....^20;
	for ( int i = 0; i < 21; i++)
	{
	
		x ^= i;
	}
	//這次for回圈后，連續的^中，相同的資料都被抵消，只剩下一個消失的那個數
	printf("%d\n", x);

}

時間復雜度:0(N),空間復雜度：0（1）

優點：演算法效率高

缺點：

只能用于查找消失的一個數，對于消失的數字過多情況不能處理，即使分組也不好，-----分組的思想在我另外一篇博客：單身狗

一般方法：折半查找法，與對比排序法

二分查找法：

• 思路

依次拿0到20中的數字 在陣列中用二分查找的方法查找

• 代碼:

   //折半查找
	for (int i = 0; i <= 20; i++)//i為要查找的數
	{
		int left = 0;//存放陣列左邊下標
		int right = sz - 1;//存放陣列右邊下標
		int mid = 0;//陣列中間資料的下標，之所以定義在外面是因為，每次for回圈，、
		           //mid生命周期結束，這樣就可以重置mid
		while (left <= right)
		{

			mid = (left + right) / 2;
			if (arr[mid] > i)//說明要找的資料在mid的左邊,排序后，左邊的資料都小于arr[mid]
			{
				right = mid - 1;
			}
			else if (arr[mid] < i)//說明要找的資料在mid的右邊,排序后，右邊的資料都小于arr[mid]
			{

				left = mid + 1;

			}
			else
			{

				break;//break,只能結束一層回圈即while,
			}
		}
		
		if (left > right)//如果i沒有在陣列中找到就輸出I
		{
			printf("%d\n", i);
		
		}
	}
	
	
}

• 時間復雜度：0（N²）空間復雜度：0（1）

• 優點可以處理消失數字多的情況，

• 缺點必須要對陣列排序，

對比排序法：

• 思想：將陣列排序后，將0到20的陣列依次與陣列

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-6L4g3Ptr-1631111664941)(前言：.assets/image-20210908164408529-16310906497221.png)]

代碼：

int main()
{

	int arr[] = { 16,17,18,19,0,1,2,3,4,5,6,7,8,9,10,11,12,14,15,20 };
	int sz = sizeof(arr) / sizeof(*arr);//計算陣列長度
	//選擇法排序
	for (int i = 0; i < sz - 1; i++)//選擇法排序陣列的思想就是，
		                           //拿第i個元素，將其與之后的資料進行比較，
		                           //拿到最小資料的下標，
	{
		int min = i;//用于存放下標
		for (int j = i + 1; j < sz; j++)
		{
			if (arr[j] < arr[min])
			{
				min = j;
			}
		}//通過此層回圈，min會得到資料最小的陣列下標

		if (min != i)//如果min得到下標不是i就交換下標i與下標min的值
		{
			int tmp = arr[i];
			arr[i] = arr[min];
			arr[min] = tmp;
		}

	}

	int flag = 0;//記錄陣列下標

	for (int i = 0; i < 21; i++)
	{

		if (i ^ arr[flag])//^后如果不相等，那么異或后就是非0，也就是i為缺少的數字
		{
			printf("%d\n",i);

		}
		else
		{

			flag++;
		}

	}


}

• 時間復雜度：0（N²）,空間復雜度：0（1）

• 優點可以實作 消失的數字多的情況

• 缺點：也是必須對陣列排序，

總結：

• 博主目前沒想到，不用按位異或的方法，不對陣列排序的情況下，找到消失的數字的方法，
• 若有那為大佬，知道這種不排序就可以找到的消失的數字方法，希望大佬能留言，非常感謝！