[Leedcode][JAVA][第41题][缺失的第一个正数][哈希表][数组]

蔚落 2023-02-20 12:29 55阅读 0赞

#### 【问题描述】\[困难\] ####

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
    
     
    
    示例 1:
    
    输入: [1,2,0]
    输出: 3
    示例 2:
    
    输入: [3,4,-1,1]
    输出: 2
    示例 3:
    
    输入: [7,8,9,11,12]
    输出: 1
     
    
    提示：
    
    你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

#### 【解答思路】 ####

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

###### 1. 哈希表思想 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
**时间复杂度：O(N) 空间复杂度：O(1)**

class Solution { 
        public int firstMissingPositive(int[] nums) { 
            int n = nums.length;
            for (int i = 0; i < n; ++i) { 
                if (nums[i] <= 0) { 
                    nums[i] = n + 1;
                }
            }
            for (int i = 0; i < n; ++i) { 
                int num = Math.abs(nums[i]);
                if (num <= n) { 
                    nums[num - 1] = -Math.abs(nums[num - 1]);
                }
            }
            for (int i = 0; i < n; ++i) { 
                if (nums[i] > 0) { 
                    return i + 1;
                }
            }
            return n + 1;
        }
    }

###### 2. 置换 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]  
**时间复杂度：O(N) 空间复杂度：O(1)**

class Solution { 
        public int firstMissingPositive(int[] nums) { 
            int n = nums.length;
            for (int i = 0; i < n; ++i) { 
                while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { 
                    int temp = nums[nums[i] - 1];
                    nums[nums[i] - 1] = nums[i];
                    nums[i] = temp;
                }
            }
            for (int i = 0; i < n; ++i) { 
                if (nums[i] != i + 1) { 
                    return i + 1;
                }
            }
            return n + 1;
        }
    }

###### 3. 不符合题意 ######

**时间复杂度：O(N) 空间复杂度：O(N)**  
**HashSet**

public int firstMissingPositive(int[] nums) { 
            int len = nums.length;
    
            Set<Integer> hashSet = new HashSet<>();
            for (int num : nums) { 
                hashSet.add(num);
            }
    
            for (int i = 1; i <= len ; i++) { 
                if (!hashSet.contains(i)){ 
                    return i;
                }
            }
    
            return len + 1;
        }

**排序遍历**  
**时间复杂度：O(N^2) 空间复杂度：O(1)**

public int firstMissingPositive(int[] nums) { 
     Arrays.sort(nums);
            int j=1;
            for(int i =0; i<nums.length;i++){ 
                if(nums[i]<=0){ 
                    continue;
                }else{ 
                    while(i+1<nums.length && nums[i] ==nums[i+1]){ 
                        i++;
                    }
                    if(nums[i] ==j ){ 
                        j++;
                    }else{ 
                        return j;
                    }
                }
            }
    
            return j;
        }

#### 【总结】 ####

###### 1.HashSet 没有的话我们提取其思想 自己干一个！ ######

###### 2.细节 ######

//数组排序
    int[] array = { 10, 3, 6, 1, 4, 5, 9};
    Arrays.sort(array);
    
    //Collections 下面主要有Set 和List
    // asList
    int[] arr = { 2,4,6,8,10};
    Integer[] arrInteger = { 2,4,6,8,10};
    List list = Arrays.asList(arr);  //list大小为1 数组类型
    List list1 = Arrays.asList(arrInteger);//list大小为1 Integer类型
    //List 逆转
    Collections.reverse(list1);//冒泡交换
    
    //List 正降序排序
    List<Integer> list = new ArrayList<Integer>(Arrays.asList(10, 3, 6, 1, 4, 5, 9));
    Collections.sort(list);
    Comparator<Integer> reverseComparator = Collections.reverseOrder();
    Collections.sort(list, reverseComparator);

###### 3.端午节假期愉快~ ######

转载链接：https://leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200627103921531.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200627103951904.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200627105334270.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70