Re: [閒聊] 每日leetcode
我好想轉職，有沒有人可以內推我去寫韌體
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
好想爪在天音妹妹的大腿上
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.109.58 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1711453857.A.B10.html
推
03/26 19:52,
1年前
, 1F
03/26 19:52, 1F
推
03/26 19:53,
1年前
, 2F
03/26 19:53, 2F
→
03/26 19:53,
1年前
, 3F
03/26 19:53, 3F
→
03/26 19:54,
1年前
, 4F
03/26 19:54, 4F
→
03/26 19:55,
1年前
, 5F
03/26 19:55, 5F
→
03/26 19:55,
1年前
, 6F
03/26 19:55, 6F
推
03/26 19:56,
1年前
, 7F
03/26 19:56, 7F
→
03/26 19:58,
1年前
, 8F
03/26 19:58, 8F
討論串 (同標題文章)
完整討論串 (本文為第 71 之 1548 篇)：