【4.5日题解】——41. 缺失的第一个正数

☘前言☘

今天的题目也许有点难了，但是吧。

也还好感觉。

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