【C語言】LeetCode面試題17.04.消失的數(shù)字的n種解法-創(chuàng)新互聯(lián)
本文涉及的庫函數(shù)或者數(shù)據(jù)結構與算法不熟悉的地方，可以在文章末找到相關知識詳解鏈接。
- 題目描述
- 解法一
- 題解代碼
- 解法二
- 題解代碼
- 解法三
- 題解代碼
- 解法四
- 題解代碼
- 總結
OJ鏈接：LeetCode 面試題 17.04. 消失的數(shù)字
數(shù)組nums包含從0到n的所有整數(shù)，但其中缺了一個。請編寫代碼找出那個缺失的整數(shù)。你有辦法在O(n)時間內完成嗎？
題目中描述，數(shù)組nums包含從0到n的所有整數(shù)，但缺少了其中一個。
那么我們可以通過等差數(shù)列求和公式，或者0-n循環(huán)求和，都可以得到總和totalNum。我們只需要再遍歷減去數(shù)組的各個元素，剩下的值就是消失的數(shù)字了。
時間復雜度O(n)，空間復雜度O(1)。
//nums是題目給我們的數(shù)組，numsSize是數(shù)組的大小
int missingNumber(int *nums, int numsSize)
{//等差數(shù)列求和公式 項數(shù)*（首項+尾項）/2
//我們要求0-n，有n+1項，首項為0，尾項為n，numsSize大小是n
int totalNum = (numsSize + 1) * (0 + numsSize) / 2;
//遍歷減去已有數(shù)
for (int i = 0; i< numsSize; i++)
totalNum -= nums[i];
//此時返回值totalNum就是missingNum
return totalNum;
}//timeO(n) spaceO(1)我們知道異或^位運算符（二進制位相同為0，相異為1）有這樣的性質：
- 數(shù)字與自己本身異或為0，5^5=0
- 數(shù)字與0異或還是自己本身，7^0=7，0二進制位全是0，和0相同的就是0，相異的就是1，不變
所以我們可以定義個數(shù)字Num=0，然后讓他與0-n各個數(shù)字遍歷異或，再把他與nums各個元素異或，存在的數(shù)字就會異或兩遍得0，不會對Num造成影響，最后只有落單的消失的數(shù)字，與Num=0異或，是Num值變?yōu)橄У臄?shù)字值。
時間復雜度O(n)，空間復雜度O(1)。
int missingNumber(int *nums, int numsSize)
{//從0-n遍歷異或一遍
int Num = 0;
for (int i = 0; i<= numsSize; i++)
Num ^= i;
//再把nums各個元素異或一遍
for (int i = 0; i< numsSize; i++)
Num ^= nums[i];
//此時的Num的值就是missingNum
return Num;
}//timeO(n) spaceO(1)nums是0-n中消失了一個數(shù)的數(shù)組，如果我們自定義一個n+1大小的數(shù)組arr并賦值為0，用nums各個元素做下標，如果數(shù)字存在，則把數(shù)組arr對應位置下標元素賦值為1，再遍歷一次查找哪個下標值為0，就找到消失的數(shù)字了。
時間復雜度O(n)，空間復雜度O(n)
int missingNumber(int *nums, int numsSize)
{//開辟一個n+1大的數(shù)組，并賦值為0
int *arr = (int *)malloc((numsSize + 1) * sizeof(int));
memset(arr,0, (numsSize + 1) * sizeof(int));
//數(shù)字存在則把對應數(shù)組下標位置賦值為1
for (int i = 0; i< numsSize; i++)
arr[nums[i]] = 1;
//當arr值為0會停止循環(huán)，此時的值就是消失的數(shù)字
int missNum = 0;
while (arr[missNum])
missNum++;
return missNum;
}//timeO(n) spaceO(n)我們還可以把數(shù)組進行快速排序，再從0開始用二分查找法遍歷查找數(shù)字是否存在。
快速排序時間復雜度O(nlogn)，空間復雜度O(logn)。
二分查找時間復雜度O(logn)，空間復雜度O(1)。
所以此題解時間復雜度O(nlogn)，空間復雜度O(logn)。
代碼可能跑不過OJ會掛。
int int_cmp(const void *e1, const void *e2)
{return *(int *)e1 - *(int *)e2;
}
int missingNumber(int *nums, int numsSize)
{//先將數(shù)組快排
qsort(nums, numsSize, sizeof(int), int_cmp);
//從0-n逐個數(shù)字二分查找, 沒查找到的數(shù)字就是
//flag用來標記數(shù)字是否查找到
int flag = 0;
int begin = 0;
int end = numsSize - 1;
int mid = (begin + end) / 2;
int missNum = 0;
for (missNum = 0; missNum<= numsSize; missNum++)
{//二分查找
while (begin<= end)
{if (nums[mid] >missNum)
{end = mid - 1;
}
else if (nums[mid]< missNum)
{begin = mid + 1;
}
else
{flag = 1;
break;
}
mid = (begin + end) / 2;
}
//沒有查找到，終止for循環(huán)
if (!flag)
{break;
}
//查找到了，初始化二分查找的基本變量，進入下次循環(huán)
else
{ begin = 0;
end = numsSize - 1;
mid = (begin + end) / 2;
flag = 0;
}
}
return missNum;
}//timeO(nlogn) spaceO(logn)解法一簡單易想，時間復雜度和空間復雜度都最佳。
解法二巧妙利用了位運算異或^的特性，十分巧妙，時間和空間復雜度也很佳，也是本文主要想介紹的解法。
解法三利用數(shù)組下標和對應元素值的映射，解法也不錯。
解法四暴力的遍歷查找，可以解決問題，但時間復雜度太高。
memset內存賦值函數(shù)詳解
qsort快速排序函數(shù)詳解
碼字不容易，歡迎關注，點贊，收藏，評論，轉發(fā)。
你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
網(wǎng)頁標題：【C語言】LeetCode面試題17.04.消失的數(shù)字的n種解法-創(chuàng)新互聯(lián)
文章鏈接：http://m.jiaotiyi.com/article/pejej.html