☘前言☘

今天的题目也许有点难了，但是吧。也还好感觉。希望有想要提高的同学跟我们一起来刷题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，显示的内存和时间复杂度却决于当前的网络情况，我在网络拥塞的情况下会发现时间高很多，就离谱呗？大家加油！