41. 缺失的第一个正数

￡神魔★判官ぃ 2022-12-07 12:43 175阅读 0赞

# 题目： #

[41. 缺失的第一个正数][41.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解： #

![在这里插入图片描述][20200916012343707.png_pic_center]

## 1. 解释一： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]

## 2. 解释二： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]

## 3. 解释三： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 7]

## 4. 解释四： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 9]

# 代码： #

public class code41 { 
    
        // tips: 正整数从1开始，初步换序后，a[0]应为1，a[1]应为2
        public static int firstMissingPositive(int[] nums) { 
            int n = nums.length;
            // 换序的过程即将数换到正确位置的过程，最多换n个，故复杂度为O(n)
            for(int i = 0; i < n; i++)
            { 
                // 该数字不属于当前位置 交换 a[i] 和 a[i]-1 位置上的数字
                while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
                { 
                    // 满足在指定范围内、并且没有放在正确的位置上，才交换
                    // 例如：数值 3 应该放在索引 2 的位置上
                    int temp = nums[nums[i] - 1];
                    nums[nums[i] - 1] = nums[i];
                    nums[i] = temp;
                }
            }
            // [1, -1, 3, 4]
            for(int i = 0; i < n; i++)
            { 
                if(nums[i] != i + 1)
                { 
                    return i + 1;
                }
            }
            // 都正确则返回数组长度 + 1
            return n + 1;
        }
    
        public static void main(String[] args) { 
            int nums1[] = { 1, 2, 0};
            int res1 = firstMissingPositive(nums1);
            System.out.println(res1);
    
            int nums2[] = { 3, 4, -1, 1};
            int res2 = firstMissingPositive(nums2);
            System.out.println(res2);
    
            int nums3[] = { 7, 8, 9, 11, 12};
            int res3 = firstMissingPositive(nums3);
            System.out.println(res3);
        }
    }

# 参考： #

1.  [缺失的第一个正数][Link 1]
2.  [原地哈希（哈希函数为：f(nums\[i\]) = nums\[i\] - 1）][f_nums_i_ _ nums_i_ - 1]
3.  [java的6种解法，其中位运算击败了100%用户][java_6_100]
4.  [【手绘图解】让nums数组承载额外的信息][nums]
5.  [C语言，时间复杂度O(n)，击败了100%的用户，空间复杂度O(1)][C_O_n_100_O_1]
6.  [JAVA双指针，精简代码，优化桶位，0ms, 时间复杂度o(n), 空间复杂度o(1)][JAVA_0ms_ _o_n_ _o_1]

[41.]: https://leetcode-cn.com/problems/first-missing-positive/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/6607ea79a12448a0afaebe0e94a9a81b.png
[20200916012343707.png_pic_center]: /images/20221123/6353b8bc46eb4aa8a503985e0b40d6bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/768bbc08ddb74232bf9735e89e8eb8ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/346a05591c2943adb648baaf893ad1ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/d9cc9126c57c41e28c773ad4bfceaa50.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/816de3aebdd14d6088d554065723068a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/68e2770714e34b38b8db59b972da0e58.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/956dcfd25e1d4a228f640132b5279ce7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/e61b2a32ee3c45fca027ef61a5fb139e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/1305207b9c1842e3b51e2be47c8f446e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/b7c94e494e41488ca921be0abb05a7e6.png
[Link 1]: https://leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
[f_nums_i_ _ nums_i_ - 1]: https://leetcode-cn.com/problems/first-missing-positive/solution/tong-pai-xu-python-dai-ma-by-liweiwei1419/
[java_6_100]: https://leetcode-cn.com/problems/first-missing-positive/solution/javade-6chong-jie-fa-de-tu-wen-xiang-jie-wei-yun-s/
[nums]: https://leetcode-cn.com/problems/first-missing-positive/solution/shou-hui-tu-jie-si-lu-de-xi-zhi-chan-shu-tong-pai-/
[C_O_n_100_O_1]: https://leetcode-cn.com/problems/first-missing-positive/solution/lei-si-ji-shu-pai-xu-by-qii404/
[JAVA_0ms_ _o_n_ _o_1]: https://leetcode-cn.com/problems/first-missing-positive/solution/javashuang-zhi-zhen-shi-jian-fu-za-du-on-kong-jian/