268 丟失的數(shù)字
題目信息
給定一個包含 [0, n] 中 n 個數(shù)的數(shù)組 nums ，找出 [0, n] 這個范圍內(nèi)沒有出現(xiàn)在數(shù)組中的那個數(shù)。
題目地址：https://leetcode.cn/problems/missing-number/
示例 1：
輸入：nums =?[3,0,1]
輸出：2
解釋：n = 3，因為有 3 個數(shù)字，所以所有的數(shù)字都在范圍?[0,3]?內(nèi)。2 是丟失的數(shù)字，因為它沒有出現(xiàn)在 nums 中。
示例 2：
輸入：nums =?[0,1]
輸出：2
解釋：n = 2，因為有 2 個數(shù)字，所以所有的數(shù)字都在范圍?[0,2]?內(nèi)。2 是丟失的數(shù)字，因為它沒有出現(xiàn)在 nums 中。
示例 3：
輸入：nums =?[9,6,4,2,3,5,7,0,1]
輸出：8
解釋：n = 9，因為有 9 個數(shù)字，所以所有的數(shù)字都在范圍?[0,9]?內(nèi)。8 是丟失的數(shù)字，因為它沒有出現(xiàn)在 nums 中。
示例 4：
輸入：nums =?[0]
輸出：1
解釋：n = 1，因為有 1 個數(shù)字，所以所有的數(shù)字都在范圍?[0,1]?內(nèi)。1 是丟失的數(shù)字，因為它沒有出現(xiàn)在 nums 中。
提示：
n?==?nums.length
1?<=?n?<=?104
0?<=?nums[i]?<=?n
nums?中的所有數(shù)字都?獨一無二
進階： 你能否實現(xiàn)線性時間復雜度、僅使用額外常數(shù)空間的算法解決此問題?
題解一
也就是有從0到n共n+1個數(shù)字: 0 1 2 ... n
給出的數(shù)組是它們之間的n個數(shù)，缺少一個要找出來。（n個數(shù)是無序的）
如果是有序的那么哪個位置的數(shù)比前一個位置的數(shù)大2，那么說明缺少了一個數(shù)字，且數(shù)字的值和位置標相等。
如果排序去做很顯然多此一舉，我們要的只是那個數(shù)字，排序的消耗更大走了彎路。這組數(shù)字本身是一組連續(xù)的數(shù)字只是無序的擺放了且缺少一個。
因此我們可以準備一個原來的卡槽（n + 1個位置），將他們一一放進去，最后哪個位置留空那么就缺這個數(shù)字
實現(xiàn)當中容器用什么都可以我采用的數(shù)組，創(chuàng)建一個n+1的卡槽，初始化里面都是0，因此只需要把有值的改為1，完成后剩下只有一個位置為0，這個位置即是缺失的數(shù)字。
public?int?missingNumber(int[]?nums)?{
????byte[]?arr?=?new?byte[nums.length?+?1];
????for(int?i?=?0;?i?<?nums.length;?i++){
????????int?num?=?nums[i];
????????arr[num]?=?1;
????}
????for(int?i?=?0;?i?<?arr.length;?i++){
????????if(arr[i]?==?0){
????????????return?i;
????????}
????}
????return?-1;
}
因為我們的數(shù)組只存0/1，節(jié)約空間所以使用byte類型（因為Java里面沒有更小的類型了），又想到可以用一個數(shù)字的每一位來存0/1就不需要數(shù)組了。但最大的long也只有64位，題目當中的n最大是104.需要105個位置。
當前題解空間復雜度達到了n.滿足不了進階的要求。
題解二
什么方法可以在當前給出的數(shù)組內(nèi)部直接得到缺失誰呢。
一段連續(xù)的數(shù)字堆在一起，只少一個...連續(xù)的數(shù)字？
求和...對就是求和，0到n的數(shù)字的和減去當前數(shù)組所有元素的和，差是多少就是多出來的數(shù)字。
//?0到n數(shù)字的和
(1+n)?*?n?/?2
代碼：
public?int?missingNumber(int[]?nums)?{
????int?len?=?nums.length;
????int?expect?=?(1?+?len)?*?len?/?2;
????for(int?i?=?0;?i?<?len;?i++){
????????//?減去每個數(shù)字
????????expect?-=?nums[i];
????}
????return?expect;
}
題解三
雖然解出了覺得比較滿意的答案，但確實有預感是有更好的解法，從0到n連續(xù)的數(shù)字索引就是它們的值沒必要額外去存儲記錄什么，可能性潛藏的已知條件太多了很有可能沒有用上。
缺少一個數(shù)字的數(shù)組和原來的完整的n + 1的數(shù)字。合在一起就是一堆數(shù)字每個都是一對且只有一個落單，這么一堆數(shù)字進行累計異或最終雙雙相消就可以得到唯一的數(shù)字。
我們不需要額外的去創(chuàng)建一個這樣的合成數(shù)組，因為數(shù)字和下標一一對應，循環(huán)一次0到n即可得到原來的這些數(shù)字進行異或，再對提供的數(shù)組進行異或即可。
public?int?missingNumber(int[]?nums)?{
????int?res?=?0;
????for?(int?i?=?0;?i?<=?nums.length;?i++){
????????res?^=?i;
????}?
????for?(int?i?:?nums)?{
????????res?^=?i;
????}
????return?res;
}
總結(jié)
這題是當前合集最后一個分類其他也是最后一題但它的類型偏向與數(shù)組，可以回顧數(shù)組的一些常規(guī)操作比如排序、哈希、原地交換等將原本數(shù)組進行整理得到新數(shù)組的手段.
異或題解參考了官方解題，想到了自己的曾經(jīng)的總結(jié)異或運算找唯一，卻在此題沒有自主發(fā)現(xiàn)。沒有充分的利用已知的數(shù)列與參數(shù)數(shù)組的關系。這和2020年9月21號解的只出現(xiàn)一次的元素異曲同工。
初級合集全部題解到此就完結(jié)了，原計劃半年到現(xiàn)在兩年了才完成，太過于懈怠了。合集過后對數(shù)組、鏈表以及樹從生疏到現(xiàn)在確實有了更多的了解再次面對時充滿了更多的思路。但數(shù)據(jù)結(jié)構(gòu)仍有待加強，算法思想需體系學習。因此不會立馬開啟下一合集的題解系列，第一是有其他方向的內(nèi)容需要學習和輸出，第二是在算法這邊開始進行系統(tǒng)的學習輸入希望日后可以帶來更好的內(nèi)容。
往期推薦
點個在看你最好看