今天的题目也许有点难了，但是吧。也还好感觉。希望有想要提高的同学跟我们一起来刷题0.0
4.5日每日一题——缺失的第一个正数
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min
全文目录
☘前言☘
解题思路1
解题思路2
解题思路3
📑写在最后
41. 缺失的第一个正数
解题思路1
简单的思路就是要求O(n)就直接hash表，你能奈我何。为了压缩一点复杂度，我们采用位hash表，就是一位代表一个元素。
unsigned char hash[70005]; int firstMissingPositive(int* nums, int numsSize){ for(int i = 0;i < numsSize/8 + 1;++i){ hash[i] = 0; } for(int i = 0;i < numsSize;++i) if(nums[i] > 0 && nums[i] < 500005) hash[nums[i]/8] |= 1<<(nums[i]%8); for(int i = 1;i < 500005;++i) if(!(hash[i/8] & 1<<(i%8))) return i; return 0; }
这结果还不香？？？？？
解题思路2
学习学习官方的解题思路，也是hash，但是为了压缩空间复杂度，采用了一种妙蛙种子的hash表。哈哈哈 其实就是给位置打标签，如果当前的元素比n+1小就给[x-1]位置打标签，同时为了不影响对应位置的信息，打标签的方式是吧对应的元素进行翻转，也就是把正的变成负的，同时为了防止之前就是负数元素的影响，将负元素全部改成n+1也就是可能的最大值。
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 n = abs(nums[i]); if(n <= numsSize) nums[n-1] = -abs(nums[n-1]); //翻转 } for(int i = 0;i < numsSize;++i) if(nums[i] > 0) return i+1; return numsSize + 1; }
就这就这？？？？空间复杂度比我直接hash还高，请问是代码段比我长么？？？？？
解题思路3
还是官方题解，这个置换方式看起来比hash优雅多了，就是每次将当前位置的元素和正确位置的元素进行置换，最后位置元素不正常的元素就是结果。
int firstMissingPositive(int* nums, int numsSize) { for (int i = 0; i < numsSize; ++i) while (nums[i] > 0 && nums[i] <= numsSize && nums[nums[i] - 1] != nums[i]) {//置换 int t = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i], nums[i] = t; } for (int i = 0; i < numsSize; ++i) if (nums[i] != i + 1) return i + 1;//返回结果 return numsSize + 1; }
感觉也不过如此啊。
📑写在最后
感觉力扣有bug，显示的内存和时间复杂度却决于当前的网络情况，我在网络拥塞的情况下会发现时间高很多，就离谱呗？大家加油！
