丟失的數字
給定一個包含 [0, n] 中 n 個數的數組 nums ，找出 [0, n] 這個范圍內沒有出現在數組中的那個數。
示例 1：

輸入：nums = [3,0,1]
輸出：2
解釋：n = 3，因為有 3 個數字，所以所有的數字都在范圍 [0,3] 內。2 是丟失的數字，因為它沒有出現在 nums 中。
示例 2：

輸入：nums = [0,1]
輸出：2
解釋：n = 2，因為有 2 個數字，所以所有的數字都在范圍 [0,2] 內。2 是丟失的數字，因為它沒有出現在 nums 中。
示例 3：

輸入：nums = [9,6,4,2,3,5,7,0,1]
輸出：8
解釋：n = 9，因為有 9 個數字，所以所有的數字都在范圍 [0,9] 內。8 是丟失的數字，因為它沒有出現在 nums 中。
示例 4：

輸入：nums = [0]
輸出：1
解釋：n = 1，因為有 1 個數字，所以所有的數字都在范圍 [0,1] 內。1 是丟失的數字，因為它沒有出現在 nums 中。

---

對于上述題目我們有幾種解法

1.將數組中的數據進行升序排序用后一個數據-上一個數據不等于1，則用后面的數據減1找到丟失的數字。

void Bubble_sort(int* arr, int sz)
{int i = 0;for (i = 0; i < sz - 1; i++)//確定排序的趟數{int j = 0;int flag = 1;//如果arr[j]<arr[j+1],就不用進入循環，加快效率for (j = 0; j < sz - 1 - i; j++){//兩兩比較，交換排序if (arr[j] > arr[j + 1]){flag = 0;//發生交換就說明無序int tmp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = tmp;}if (flag == 1)//沒有進入循環break;}}
}
void FindMissNum(int* arr, int n)
{Bubble_sort(arr , n);for (int i = 0; i < n; ++i){if (i + 1 == n)//防止越界{break;}if ((arr[i + 1]- arr[i])!=1 ){printf("丟失的數字為%d\n", arr[i + 1]-1);break;}	}
}
int main()
{int num[] = { 3,1,0,2,4,9,5,6,7,10 };int sz = sizeof(num)/sizeof(num[0]);FindMissNum(num, sz);return 0;
}

雖然上述代碼可以解決問題，但是時間復雜度為O（n），效率低

---

2.將數組中0-（n-1）的數據相加得到num1，再將0-n的數據相加得到num2，將num2-num1得出的結果就是丟失的數字。

void FindMissNum2(int* arr, int sz)
{int i = 0;int j = 0;int sum1 = 0; int sum2 = 0;for (i = 0; i < sz; i++)//將數組中的所以數據相加{int tmp1 = arr[i];sum1 = tmp1 + sum1;}for (j = 0; j < sz +1; j++)//將0~n的數字相加{int tmp2 = j;sum2 = tmp2+sum2;}int missnum = sum2 - sum1;printf("丟失的數字是%d\n",missnum);
}
int main()
{int num[] = { 3,1,0,2,4,9,5,6,7,10 };int sz = sizeof(num)/sizeof(num[0]);FindMissNum2(num, sz);return 0;
}

上述代碼的時間復雜度為O（1），空間復雜度為O（n），不推薦

---

3.將數組中的數據全部異或,再與0-n全部異或，得出的結果就是丟失的數字。
（原理：任何數字異或自己之后就會抵消，異或的交換律）

void FindMissNum3(int* arr, int sz)
{int tmp1  =  0;int tmp2  =  0;for (int i = 0; i < sz; ++i){tmp1 = tmp1 ^ arr[i];}for (int j = 0; j < sz + 1; j++){tmp2 = tmp2 ^ j;}int missnum = tmp1 ^ tmp2;printf("丟失的數字是%d\n", missnum);
}
int main()
{int num[] = { 3,1,0,2,4,9,5,6,8,10 };int sz = sizeof(num)/sizeof(num[0]);FindMissNum3(num,sz);return 0;
}

上述代碼的時間復雜度為O（1），且空間復雜度也為O（1），推薦使用