我好想轉職，有沒有人可以內推我去寫韌體
41. First Missing Positive
有一個array nums，請問第一個沒有在nums裡面的正整數是多少?
請用o(n)時間複雜度、o(1)空間複雜度
思路 :
負數不重要
第一個沒出現的正整數如果是x，那代表1~x-1都有在nums裡面
假設nums的長度為n，那最大可能的答案就是n+1
原本我的解法是建立1個n+1的bool矩陣
將有出現在nums裡不為負數、<=n+1的值設成true，最後去找第一個值為false的index
那個就是答案
不過題目要求要用o(1)空間複雜度
所以改成將nums裡所有負數的值改成n+1
接著去找小於nums[i]<n+1，並把nums[nums[i]-1]=-nums[nums[i]-1]
最後去找第一個i，nums[i]>0，這樣i+1就是答案
如果都是負數答案就是n+1
C code
int firstMissingPositive(int* nums, int numsSize) {
for (int i=0;i<numsSize;i++){
if (nums[i]<=0){
nums[i]=numsSize+1;
}
}
for (int i=0;i<numsSize;i++){
int temp=nums[i];
if (nums[i]<0){
temp=-temp;
}
//nums[temp-1]>0 避免已經改過的值重複修改變成正數，所以負數不進行修改
if (temp<=numsSize && nums[temp-1]>0){
nums[temp-1]=-nums[temp-1];//要-1是因為index從0開始
}
}
for (int i=0;i<numsSize;i++){
if (nums[i]>0){
return i+1;
}
}
return numsSize+1;
}
我在寫這題的時候剛好在聽天音妹妹的3D LIVE
好想爪在天音妹妹的大腿上