博文中会简要介绍Leetcode P0041题目分析及解题思路。
“First Missing Positive”是一道比较巧妙的题，题目难度其实不难，但是要想保证在O(1)的空间复杂度内完成需要一些技巧。
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0] Output: 3Example 2:
Input: [3,4,-1,1] Output: 2Example 3:
Input: [7,8,9,11,12] Output: 1Follow up:
Your algorithm should run in O(n) time and uses constant extra space.
最简单的算法是用HashSet记录一遍出现过的数，然后从1开始遍历直到直到HashSet里没有出现过这个数，则返回。
降低空间复杂度的方法是用数组下标来代表元素的值，即元素值为num的应当存储在num-1的位置，那么数组前k个中没有missing的元素则很容易得出，每个元素应该恰好在自己应当出现的位置，即num-1。反之如果存在missing则会出现一个元素不等于它的下标加1，那么可知这个元素是缺失的。而那些大于数组长度的元素会被放在前k个被恰当放置的元素之后，并且不会越界。
以下是Java的题解代码实现。
class Solution {
public int firstMissingPositive(int[] nums) {
// Time: O(n), Space: O(n)
/**
if (nums == null || nums.length == 0)
return 1;
Set<Integer> numSet = new HashSet<>();
for (int num: nums) {
if (num > 0)
numSet.add(num);
}
int missing = 1;
while (numSet.contains(missing)) {
++missing;
}
return missing;
*/
// Time: O(n), Space: O(n)
if (nums == null || nums.length == 0)
return 1;
int len = nums.length;
for (int idx=0; idx<len; ++idx) {
int num = nums[idx];
while (num > 0 && num < len && nums[num-1] != num) {
nums[idx] = nums[num-1];
nums[num-1] = num;
num = nums[idx];
}
}
for (int idx=0; idx<len; ++idx) {
if (idx+1 != nums[idx])
return idx+1;
}
return len+1;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
if (nums.size() == 0)
return 1;
for (int idx=0; idx<nums.size(); ++idx) {
int num = nums[idx];
while (num > 0 && num < nums.size() && nums[num-1] != num) {
nums[idx] = nums[num-1];
nums[num-1] = num;
num = nums[idx];
}
}
for (int idx=0; idx<nums.size(); ++idx) {
if (nums[idx] != idx+1)
return idx+1;
}
return nums.size()+1;
}
};