Leetcode(41) First Missing Positive

发表于 | 更新于 | 分类于

Description

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

1
2
Input: [1,2,0]
Output: 3

Example 2:

1
2
Input: [3,4,-1,1]
Output: 2

Example 3:

1
2
Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

解法

这道题要求时间复杂度为O(n)，所以不可能先做复杂的诸如排序之类的预处理。那么可以采取巧妙的哈希方法，建立一个哈希表，首先扫描一遍数组，将元素插入到哈希表中，并记录这个数组的最大值。之后从1开始到最大值，只要出现了谁不在哈希表里，即为所需要的正数。然而这种方法需要额外的空间（哈希表）。

那么利用同样的思想，将方法做些许的改进，不开额外的空间，利用数组自身进行哈希。具体实现方法是，将x存入index为x-1的位置，即nums[i] = i+1;最后从头到尾扫描数组，若某个槽不满足这个条件，那么寻找的正整数就是index+1了。挺神奇的。为了构建这个数组，需遍历一遍数组，对每个槽，将槽中元素交换到指定位置，知道数组中没有现在槽中元素所对应的位置，处理下一个槽。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

}

利用哈希结构的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int firstMissingPositive(int[] nums) {
        if(nums == null){
            return -1;
        }
        HashMap<Integer,Integer> helper = new HashMap<>();
        for(int i = 0;i<nums.length;i++){
            if(nums[i]>0){
                helper.put(nums[i],nums[i]);
            }
        }
        for(int i = 1;;i++){
            if(!helper.containsKey(i)){
                return i;
            }
        }

    }
}