leetcode41. 缺失的第一个正数

leetcode41. 缺失的第一个正数

八月 13, 2020

leetcode41. 缺失的第一个正数

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

示例 1:
输入: [1,2,0]
输出: 3

示例 2:
输入: [3,4,-1,1]
输出: 2

示例 3:
输入: [7,8,9,11,12]
输出: 1

提示：
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

难点在于如何不使用额外空间。
如果使用额外空间，会开一个hash表，然后从1开始遍历hash表，如果这个位置没有值，就是最小的正整数。对于此题，有一个特点，那就是 长度为N的数组，存储的最多的连续正整数是N个，如果从1开始存入数据，最小的正整数是N+1 。那么如果就可以利用这个特性， 大于N的和小于等于0的数全不要，在数组能表示范围内的数才保留，并且对应的数存在对应的位置上 ，这样最后遍历数组，如果某个位置上没有数，就返回这个值，如果整个数组是满的，返回N+1。
比如[3,4,-1,1]->[1,-1,3,4 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > 0 && nums[i] <= nums.length) {//在1~N的范围内才处理
               
                if (nums[i] == nums[nums[i] - 1]) {
                //防止死循环，一个数在某一个位置有了就不用动了
                //不过如果这个数本来就在属于他的地方，应该break
                 if (i + 1 == nums[i]) break;
                    nums[i] = 0;
                    break;
                }
                //交换
                int t = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = t;
            }
            
        }
        //show(nums);
        for (int i = 0; i < nums.length; i++) {//不在范围内的说明该位置为空
            if (nums[i] <= 0 || nums[i] > nums.length) return i + 1;
        }
        return nums.length + 1;
    }
    public void show(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

leetcode 115