LeetCode41 缺失的第一个正数

题目

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

 示例 1： 
输入：nums = [1,2,0]
输出：3
 示例 2： 
输入：nums = [3,4,-1,1]
输出：2
 示例 3： 
输入：nums = [7,8,9,11,12]
输出：1

 提示： 
 1 <= nums.length <= 5 * 10? 
 -231 <= nums[i] <= 231 - 1 

方法

哈希法

1.把负数都变成length+1
2.把对应下标的值变为负数
3.找到第一个正数

• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
    public int firstMissingPositive(int[] nums) {
        int length = nums.length;
        for(int i=0;i0){
                return i+1;
            }
        }
        return length+1;
    }
}

置换法

1. 把数字换到她对应的下标上
2. 找到第一个下标不对应的

• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
    public int firstMissingPositive(int[] nums) {
        int length = nums.length;
        for(int i=0;i0&&nums[i]