First Missing Positive 解答

Question

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

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

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

Solution 1 -- HashSet

Note the problem is to find first missing integer, ie, if input is [4,5,7,8], we should return 1.

Naive way is to traverse from 1 to length, find whether they are in original input set. Time complexity O(n), space cost O(n).

 1 public class Solution {
 2     public int firstMissingPositive(int[] nums) {
 3         int length = nums.length;
 4         Set<Integer> set = new HashSet<Integer>();
 5         for (int i = 0; i < length; i++)
 6             set.add(nums[i]);
 7         int result = 1;
 8         for (int i = 1; i <= length; i++) {
 9             if (!set.contains(i)) {
10                 result = i;
11                 break;
12             } else {
13                 // Should increase here
14                 // Consider input [1]
15                 result++;
16             }
17         }
18         return result;
19     }
20 }

Solution 2

Key is to put i on position (i - 1). Time complexity O(n), space cost O(1).

 1 public class Solution {
 2     public int firstMissingPositive(int[] nums) {
 3         int length = nums.length;
 4         // Put i on (i - 1) position
 5         // Consider three conditions: 1. nums[i] <= 0 2. nums[i] > length 3. duplicates
 6         for (int i = 0; i < length; i++) {
 7             int target = nums[i];
 8             if (target != i + 1) {
 9                 // nums[i] <= 0 nums[i] > length
10                 if (target <= 0 || target > length)
11                     continue;
12                 // Duplicate
13                 if (nums[target - 1] == target) {
14                     nums[i] = 0;
15                     continue;
16                 }
17                 // Swap target with nums[target - 1]
18                 int tmp = nums[target - 1];
19                 nums[target - 1] = target;
20                 nums[i] = tmp;
21                 // Still need to check nums[i] after swap;
22                 i--;
23             }
24         }
25         
26         int result = length + 1;
27         // Check
28         for (int i = 0; i < length; i++) {
29             if (nums[i] != i + 1) {
30                 result = i + 1;
31                 break;
32             }
33         }
34         return result;
35     }
36 }