楼主:
JIWP (JIWP)
2024-03-26 19:50:55我好想转职，有没有人可以内推我去写韧体
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
好想爪在天音妹妹的大腿上