Related:
Lintcode 570 - Find the Missing Number II
LeetCode 41 - First Missing Positive
LintCode 196 - Find the Missing Number I
LeetCode 287 - Find the Duplicate Number - Google Interview
http://n00tc0d3r.blogspot.com/2013/03/find-first-missing-positive.html
2) Now we can ignore non-positive elements and consider only the part of array which contains all positive elements. We traverse the array containing all positive numbers and to mark presence of an element x, we change the sign of value at index x to negative. We traverse the array again and print the first index which has positive value. In the following code, findMissingPositive() function does this part. Note that in findMissingPositive, we have subtracted 1 from the values as indexes start from 0 in C.
https://leetcode.com/discuss/4220/a-very-nice-solution-from-ants-aasma-%40stackoverflowIn this case 1st array will rearrange as
-21 -10 24 23 27 26 28 15
now we will start from index 2 considering index at value 24 is 0 and size is 6 as each positive value is greater than size this condition will not be satisfied
abs(arr[i]) - 1 < size
so in next loop when we start from index 0 that is element 24 we will get value positive at that point only and index is 0
so we will return i+1 that is 0+1
so 1 will be returned which is smallest positive missing integer
In other word, “all the numbers are in their correct positions”. What are correct positions? For any i, A[i] = i+1. So our goal is to rearrange those numbers (in place) to their correct positions. We then need to decide how to arrange them. Let’s take the [3, 4, -1, 1] as an example. The 1st number, 3, we know it should stay in position 2. So we swap A[0] = 3 with A[2]. We then get [-1, 4, 3, 1]. We can’t do anything about -1 so we leave it there. The 2nd number, 4, we know it should sit in A[3]. So we swap A[1] = 4 with A[3]. We then get [-1, 1, 3, 4]. Now 1 should stay in A[0], so we keep swapping and we get [1, -1, 3, 4]. Notice now every positive number is staying in their correct position (A[0]=1, A[2]=3 and A[3]=4). We then need one more scan to find out 2 is missing.
Then, how to solve this?
Let's take another look at the problem. It is asking for the first missing POSITIVE integer.
So, given a number in the array,
public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if (A==null||A.length==0) return 1;
int i=0;
while (i<A.length){
// Strongly be care of that beside check A[i]!=i, also check A[A[i]]!=A[i]
// in case [1,1], if only check A[i]=i, there will be infinity loop
if (0<=A[i] &&A[i]<A.length&&A[i]!=i&&A[A[i]]!=A[i]){
// must assign A[A[i]] to temp instead of A[i] to temp or will infinity loop
// int temp=A[i];
// A[i]=A[A[i]];
//A[A[i]]=temp;
// see A[i] in A[A[i]] and A[i] has been changed
// so temp will never been sign to the place you want
int temp=A[A[i]];
A[A[i]]=A[i];
A[i]=temp;
}
else{
i++;
}
}
for (int j=1; j<A.length; j++){
if (A[j]!=j) return j;
}
// after above for loop mean for each position the value is equal to its index
// then if A[0]==A.length mean the missing position should be A.length+1
// the missing position is A.length;
if (A[0]==A.length) return A.length+1;
else {
return A.length;
}
}
https://leetcode.com/discuss/28531/o-1-space-java-solution
public int firstMissingPositive(int[] A) { int i = 0; while(i < A.length){ if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length) i++; else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1); else i++; } i = 0; while(i < A.length && A[i] == i+1) i++;//\\ return i+1;//\\ }
https://leetcode.com/discuss/60525/100%25-fast-elegant-java-index-based-solution-with-explanation
http://blog.csdn.net/kenden23/article/details/17099987
http://blog.csdn.net/kenden23/article/details/17099987
Also refer to http://tianrunhe.wordpress.com/2012/07/15/finding-the-1st-missing-positive-int-in-an-array-first-missing-positive/
http://www.geeksforgeeks.org/find-the-smallest-positive-number-missing-from-an-unsorted-array/
Read full article from LeetCode - First Missing Positive | Darren's Blog
Lintcode 570 - Find the Missing Number II
LeetCode 41 - First Missing Positive
LintCode 196 - Find the Missing Number I
LeetCode 287 - Find the Duplicate Number - Google Interview
http://n00tc0d3r.blogspot.com/2013/03/find-first-missing-positive.html
Given an unsorted integer array, find the first missing positive integer.
For example,
Given
and
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.
A O(n) time and O(1) extra space solution:
If we can't update the input and use extra space: bisection.
X. Bucket sort
https://leetcode.com/problems/first-missing-positive/discuss/17272/Simple-O(n)-JAVA-solution-based-on-Bucket-Sort
The basic idea is from bucket sort, which means putting every element A[i] to the position A[i] - 1, and then check the positive integer from position 0.
https://leetcode.com/problems/first-missing-positive/discuss/17272/Simple-O(n)-JAVA-solution-based-on-Bucket-Sort
The basic idea is from bucket sort, which means putting every element A[i] to the position A[i] - 1, and then check the positive integer from position 0.
The basic idea is to traversal and try to move the current value to position whose index is exactly the value (swap them). Then travelsal again to find the first unusal value, which can not be corresponding to its index.
public int firstMissingPositive(int[] nums) {
int i = 0, n = nums.length;
while (i < n) {
// If the current value is in the range of (0,length) and it's not at its correct position,
// swap it to its correct position.
// Else just continue;
if (nums[i] >= 0 && nums[i] < n && nums[nums[i]] != nums[i])
swap(nums, i, nums[i]);
else
i++;
}
int k = 1;
// Check from k=1 to see whether each index and value can be corresponding.
while (k < n && nums[k] == k)
k++;
// If it breaks because of empty array or reaching the end. K must be the first missing number.
if (n == 0 || k < n)
return k;
else // If k is hiding at position 0, K+1 is the number.
return nums[0] == k ? k + 1 : k;
} public int firstMissingPositive(int[] A) {
int i = 0;
while(i < A.length){
if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length) i++;
else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1);
else i++;
}
i = 0;
while(i < A.length && A[i] == i+1) i++;
return i+1;
}
其实这道题目才算是第一题的 follow-up。最主要的区别就在于数组内数性质的变化，不再保证是基本连续的正整数了，其中可能会有负数和重复出现的数。但是利用桶排序的思路并没有变化，只是我们在做交换时需要更多的检查而已。类似于第一题中我们移动在数组中有位置的数，把当做一个「锚」，在这里，我们把所有的负数、重复出现的数，以及在数组范围之外的数当做「锚」。
在这里，我们做了一点小处理，那就是把所有正整数在数组的位置都提前一位了，比如把
5放在A[4]，这样可以让整体的逻辑更清晰一点儿，减少出错的机会。
此外，最容易出错的地方就是没有考虑重复数字出现的可能了。如果没有考虑到这一点，内层循环就会陷入到一个死循环当中。这一点也很好想，假设有一个数出现了两次，其中一个正好在它对应的位置上，当遍历到另外一个时，由于肯定与当前位置不符，就需要交换，而换回来的数就是还是它，这就导致了死循环。
The key here is to use swapping to keep constant space and also make use of the length of the array, which means there can be at most n positive integers. So each time we encounter an valid integer, find its correct position and swap. Otherwise we continue.
public int firstMissingPositive(int[] A) {
int i = 0;
while(i < A.length){
if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length) i++;
else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1);
else i++;
}
i = 0;
while(i < A.length && A[i] == i+1) i++;
return i+1;
}
private void swap(int[] A, int i, int j){
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
X. 解法二 标记
同样的，我们先考虑如果可以有额外的空间该怎么做。
还是一样，对于 nums = [ 3 4 -1 1 8] ，我们创建一个等大的数组 a，初始化为 [ false，false，false，false，false ]。然后如果 nums 里有 1 就把，第一个位置 a [ 0 ] 改为 true。如果 nums 里有 m ，就把 a [ m - 1 ] 改为 true。看下具体的例子。
nums = [ 3 4 -1 1 8]
nums [ 0 ] 等于 3，更新 a [ false，false，true，false，false ]。
nums [ 1 ] 等于 4，更新 a [ false，false，true，true，false ] 。
nums [ 2 ] 等于 - 1，不是正数，忽略。
nums [ 3 ] 等于 1，更新 a [ true，false，true，true，false ] 。
nums [ 4 ] 等于 8，我们的 a 数组只能存 1 到 5，所以同样忽略。
然后遍历数组 a ，如果 a [ i ] != true。那么，我们就返回 i + 1。因为 a [ i ] 等于 true 就意味着 i + 1 存在。
问题又来了，其实我们没有额外空间，我们只能利用原来的数组 nums。
同样我们直接把 nums 用作数组 a。
但当我们更新的时候，如果直接把数组的数赋值成 true，那么原来的数字就没了。这里有个很巧妙的技巧。
考虑到我们真正关心的只有正数。开始 a 数组的初始化是 false，所以我们把正数当做 false，负数当成 true。如果我们想要把 nums [ i ] 赋值成 true，如果 nums [ i ] 是正数，我们直接取相反数作为标记就行，如果是负数就不用管了。这样做的好处就是，遍历数字的时候，我们只需要取绝对值，就是原来的数了。
当然这样又带来一个问题，我们取绝对值的话，之前的负数该怎么办？一取绝对值的话，就会造成干扰。简单粗暴些，我们把正数都放在前边，我们只考虑正数。负数和 0 就丢到最后，遍历的时候不去遍历就可以了。
看下具体的例子。
nums = [ 3 4 -1 1 8]
先把所有正数放前边，并且只考虑正数。nums = [ 3 4 1 8 ]，正数当作 false，负数当做 true。所以 nums 就可以看成 [ false，false，false，false ]。
nums [ 0 ] 等于 3，把第 3 个位置的数字变为负数， 更新 nums [ 3， 4， - 1， 8 ]，可以看做 [ false，false，true，false]。
nums [ 1 ] 等于 4，把第 4 个位置的数字变为负数，更新 nums [ 3， 4， - 1， - 8 ]，可以看做 [ false，false，true，true] 。
nums [ 2 ] 等于 - 1，取绝对值为 1，把第 1 个位置的数字变为负数，更新 nums [ - 3， 4， - 1， - 8 ]，可以看做 [ true，false，true，true] 。
nums [ 3 ] 等于 - 8，取绝对值为 8，我们的 nums 数组只考虑 1 到 4，所以忽略。
最后再遍历 nums，如果 nums [ i ] 大于 0，就代表缺失了 i + 1。因为正数代表 false。
把正数移到最前边，写了两种算法
public int firstMissingPositive(int[] nums) {
int n = nums.length;
//将正数移到前边，并且得到正数的个数
int k = positiveNumber(nums);
for (int i = 0; i < k; i++) {
//得到要标记的下标
int index = Math.abs(nums[i]) - 1;
if (index < k) {
//判断要标记的位置的数是不是小于 0，不是小于 0 就取相反数
int temp = Math.abs(nums[index]);
nums[index] = temp < 0 ? temp : -temp;
}
}
//找到第一个大于 0 的位置
for (int i = 0; i < k; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return k + 1;
}
private int positiveNumber(int[] nums) {
//解法一 把负数和 0 全部交换到最后
/* int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] <= 0) {
swap(nums, i, n - 1);
n--;
if (i == n) {
break;
}
}
}
return n;*/
//解法二 用一个指针 p ，保证 p 之前的都是正数。遍历 nums，每遇到一个正数就把它交换到 p 指针的位置，并且 p 指针后移
int n = nums.length;
int p = 0;
for (int i = 0; i < n; i++) {
if (nums[i] > 0) {
swap(nums, i, p);
p++;
}
}
return p;
}
The basic idea is for any k positive numbers (duplicates allowed), the first missing positive number must be within [1,k+1]. The reason is like you put k balls into k+1 bins, there must be a bin empty, the empty bin can be viewed as the missing number.
- Unfortunately, there are 0 and negative numbers in the array, so firstly I think of using partition technique (used in quick sort) to put all positive numbers together in one side. This can be finished in O(n) time, O(1) space.
- After partition step, you get all the positive numbers lying within A[0,k-1]. Now, According to the basic idea, I infer the first missing number must be within [1,k+1]. I decide to use A[i] (0<=i<=k-1) to indicate whether the number (i+1) exists. But here I still have to main the original information A[i] holds. Fortunately, A[i] are all positive numbers, so I can set them to negative to indicate the existence of (i+1) and I can still use abs(A[i]) to get the original information A[i] holds.
- After step 2, I can again scan all elements between A[0,k-1] to find the first positive element A[i], that means (i+1) doesn't exist, which is what I want.
public int firstMissingPositive(int[] A) {
int n=A.length;
if(n==0)
return 1;
int k=partition(A)+1;
int temp=0;
int first_missing_Index=k;
for(int i=0;i<k;i++){
temp=Math.abs(A[i]);
if(temp<=k)
A[temp-1]=(A[temp-1]<0)?A[temp-1]:-A[temp-1];
}
for(int i=0;i<k;i++){
if(A[i]>0){
first_missing_Index=i;
break;
}
}
return first_missing_Index+1;
}
public int partition(int[] A){
int n=A.length;
int q=-1;
for(int i=0;i<n;i++){
if(A[i]>0){
q++;
swap(A,q,i);
}
}
return q;
}
https://leetcode.com/problems/first-missing-positive/discuss/17214/Java-simple-solution-with-documentation
This code takes advantage of two insights:
- Numbers greater then n can be ignored because the missing integer must be in the range 1..n+1
- If each cell in the array were to contain positive integers only, we can use the negative of the stored number as a flag to mark something (in this case the flag indicates this index was found in some cell of the array)
public int firstMissingPositive(int[] nums) { int n = nums.length; // 1. mark numbers (num < 0) and (num > n) with a special marker number (n+1) // (we can ignore those because if all number are > n then we'll simply return 1) for (int i = 0; i < n; i++) { if (nums[i] <= 0 || nums[i] > n) { nums[i] = n + 1; } } // note: all number in the array are now positive, and on the range 1..n+1 // 2. mark each cell appearing in the array, by converting the index for that number to negative for (int i = 0; i < n; i++) { int num = Math.abs(nums[i]); if (num > n) { continue; } num--; // -1 for zero index based array (so the number 1 will be at pos 0) if (nums[num] > 0) { // prevents double negative operations nums[num] = -1 * nums[num]; } } // 3. find the first cell which isn't negative (doesn't appear in the array) for (int i = 0; i < n; i++) { if (nums[i] >= 0) { return i + 1; } } // 4. no positive numbers were found, which means the array contains all numbers 1..n return n + 1; }
public int firstMissingPositive(int[] A) {
if (A == null || A.length == 0) {
return 1;
}
int start = 0, end = A.length - 1;
while (start <= end) {
while (start < A.length && A[start] > 0) {
start++;
}
while (end >= 0 && A[end] <= 0) {
end--;
}
if (start <= end) {
int temp = A[start];
A[start] = A[end];
A[end] = temp;
}
}
for (int i = 0; i < start; i++) {
if (Math.abs(A[i]) <= A.length && A[Math.abs(A[i]) - 1] > 0) {
A[Math.abs(A[i]) - 1] = -A[Math.abs(A[i]) - 1];
}
}
for (int i = 0; i < start; i++) {
if (A[i] > 0) {
return i + 1;
}
}
return start + 1;
}
The idea is similar to this post. We use array elements as index. To mark presence of an element x, we change the value at the index x to negative. But this approach doesn’t work if there are non-positive (-ve and 0) numbers. So we segregate positive from negative numbers as first step and then apply the approach.
Following is the two step algorithm.
1) Segregate positive numbers from others i.e., move all non-positive numbers to left side.
1) Segregate positive numbers from others i.e., move all non-positive numbers to left side.
2) Now we can ignore non-positive elements and consider only the part of array which contains all positive elements. We traverse the array containing all positive numbers and to mark presence of an element x, we change the sign of value at index x to negative. We traverse the array again and print the first index which has positive value. In the following code, findMissingPositive() function does this part. Note that in findMissingPositive, we have subtracted 1 from the values as indexes start from 0 in C.
/* Utility function that puts all non-positive (0 and negative) numbers on left side of arr[] and return count of such numbers */ int segregate (int arr[], int size) { int j = 0, i; for(i = 0; i < size; i++) { if (arr[i] <= 0) { swap(&arr[i], &arr[j]); j++; // increment count of non-positive integers } } return j; } /* Find the smallest positive missing number in an array that contains all positive integers */ int findMissingPositive(int arr[], int size) { int i; // Mark arr[i] as visited by making arr[arr[i] - 1] negative. Note that // 1 is subtracted because index start from 0 and positive numbers start from 1 for(i = 0; i < size; i++) { if(abs(arr[i]) - 1 < size && arr[abs(arr[i]) - 1] > 0) arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]; } // Return the first index value at which is positive for(i = 0; i < size; i++) if (arr[i] > 0) return i+1; // 1 is added becuase indexes start from 0 return size+1; } /* Find the smallest positive missing number in an array that contains both positive and negative integers */ int findMissing(int arr[], int size) { // First separate positive and negative numbers int shift = segregate (arr, size); // Shift the array and call findMissingPositive for // positive part return findMissingPositive(arr+shift, size-shift); }
-21 -10 24 23 27 26 28 15
now we will start from index 2 considering index at value 24 is 0 and size is 6 as each positive value is greater than size this condition will not be satisfied
abs(arr[i]) - 1 < size
so in next loop when we start from index 0 that is element 24 we will get value positive at that point only and index is 0
so we will return i+1 that is 0+1
so 1 will be returned which is smallest positive missing integer
In other word, “all the numbers are in their correct positions”. What are correct positions? For any i, A[i] = i+1. So our goal is to rearrange those numbers (in place) to their correct positions. We then need to decide how to arrange them. Let’s take the [3, 4, -1, 1] as an example. The 1st number, 3, we know it should stay in position 2. So we swap A[0] = 3 with A[2]. We then get [-1, 4, 3, 1]. We can’t do anything about -1 so we leave it there. The 2nd number, 4, we know it should sit in A[3]. So we swap A[1] = 4 with A[3]. We then get [-1, 1, 3, 4]. Now 1 should stay in A[0], so we keep swapping and we get [1, -1, 3, 4]. Notice now every positive number is staying in their correct position (A[0]=1, A[2]=3 and A[3]=4). We then need one more scan to find out 2 is missing.
public int firstMissingPositive(int[] A) { if (A == null || A.length == 0) return 1; int n = A.length; // Put A[i] (>0) at index A[i]-1 for (int i = 0; i < n; i++) { if (A[i] <= n && A[i] > 0 && A[A[i]-1] != A[i]) { // Swap A[i] and A[A[i]-1]; note the sequence int temp = A[A[i]-1]; A[A[i]-1] = A[i]; A[i] = temp; // Process A[i] in the next round i--;//\\ } } // Check the first occurrence of A[i] != i+1 // If exists, i+1 is the first missing positive; otherwise, the numbers // are the first n positve numbers, the first missing one is n+1 for (int i = 0; i < n; i++) { if (A[i] != i+1) return i+1; } return n+1; }https://leetcodenotes.wordpress.com/2013/07/17/first-missing-positive/
- 如果A[i]不在自己该在的地方，就想办法把他换到该在的地方。如果A[i]是<=0或者A[i]比数组长度还大，说明没有它该在的地方，那就skip他，弄下一个（不用担心当前位置被它占了，如果后面有想在这个位置的正整数，它会被换走的）
- A[i]和A[A[i] – 1]换，然后继续回到i，接着换，直到第一种情况满足。但是如果这俩数一样，换也没用，就别原地打转了。
- 最后过一遍shift过的array，第一个不在原位的就是。
public int firstMissingPositive(int[] A) {
for (int i = 0; i < A.length; i++) {
//if it's not in its supposed to be place (the index of value x should be x - 1)
if (i != A[i] - 1){
if (A[i] <= 0 || A[i] > A.length || A[i] == A[A[i] - 1])
continue;
else {
//put A[i] to A[A[i] - 1]
swap(A, i, A[i] - 1);
i--; //回到刚才这位接着做
}
}
}
for (int i = 0; i < A.length; i++) {
if (i != A[i] - 1)
return i + 1;
}
return A.length + 1;
}
http://n00tc0d3r.blogspot.com/2013/03/find-first-missing-positive.html
A few quick thoughts:
- Sort all numbers and iterate through to find the first missing integer? No, most sorting algorithms take time at least O(nlogn).
- How about linear sorting algorithm? No, bucket sort requires O(n) space.
- Mapping all positive integers to a hash table and iterate from 1 to the length of the array to find out the first missing one? No, hash table requires O(n) space.
Then, how to solve this?
Let's take another look at the problem. It is asking for the first missing POSITIVE integer.
So, given a number in the array,
- if it is non-positive, ignore it;
- if it is positive, say we have A[i] = x, we know it should be in slot A[x-1]! That is to say, we can swap A[x-1] with A[i] so as to place x into the right place.
We need to keep swapping until all numbers are either non-positive or in the right places. The result array could be something like [1, 2, 3, 0, 5, 6, ...]. Then it's easy to tell that the first missing one is 4 by iterate through the array and compare each value with their index.
Also http://ying.ninja/?p=958- if it is non-positive, ignore it;
- if it is positive, say we have A[i] = x, we know it should be in slot A[x-1]! That is to say, we can swap A[x-1] with A[i] so as to place x into the right place.
- Since we only touch each value O(1) times, either swap it with another or check it with its index, this algorithm runs in time O(n) and use constant space.
public int firstMissingPositive(int[] A) {
// in-place swap (bucket sort)
int i = 0;
while (i < A.length) { //\\
if (A[i] > 0 && A[i] <= A.length && A[i] != i+1 && A[i] != A[A[i]-1]) {
int temp = A[A[i]-1];
A[A[i]-1] = A[i];
A[i] = temp;
} else {
++i;
}
}
// find the first positive missing integer
i = 0;
while (i < A.length && A[i] == i+1) ++i;
return i+1;
}
II:
public int firstMissingPositive(int[] A) {
// in-place swap (bucket sort)
for (int i=0; i<A.length; ++i) {
while (A[i] > 0 && A[i] <= A.length && A[i] != i+1 && A[i] != A[A[i]-1]) {
int temp = A[A[i]-1];
A[A[i]-1] = A[i];
A[i] = temp;
}
}
// find the first positive missing integer
int index = 0;
while (index < A.length && A[index] == index+1) ++index;
return index+1;
}
http://rleetcode.blogspot.com/2014/01/first-missing-positive-java.htmlpublic int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if (A==null||A.length==0) return 1;
int i=0;
while (i<A.length){
// Strongly be care of that beside check A[i]!=i, also check A[A[i]]!=A[i]
// in case [1,1], if only check A[i]=i, there will be infinity loop
if (0<=A[i] &&A[i]<A.length&&A[i]!=i&&A[A[i]]!=A[i]){
// must assign A[A[i]] to temp instead of A[i] to temp or will infinity loop
// int temp=A[i];
// A[i]=A[A[i]];
//A[A[i]]=temp;
// see A[i] in A[A[i]] and A[i] has been changed
// so temp will never been sign to the place you want
int temp=A[A[i]];
A[A[i]]=A[i];
A[i]=temp;
}
else{
i++;
}
}
for (int j=1; j<A.length; j++){
if (A[j]!=j) return j;
}
// after above for loop mean for each position the value is equal to its index
// then if A[0]==A.length mean the missing position should be A.length+1
// the missing position is A.length;
if (A[0]==A.length) return A.length+1;
else {
return A.length;
}
}
https://leetcode.com/discuss/28531/o-1-space-java-solution
public int firstMissingPositive(int[] A) { int i = 0; while(i < A.length){ if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length) i++; else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1); else i++; } i = 0; while(i < A.length && A[i] == i+1) i++;//\\ return i+1;//\\ }
https://leetcode.com/discuss/60525/100%25-fast-elegant-java-index-based-solution-with-explanation
http://blog.csdn.net/kenden23/article/details/17099987
int firstMissingPositive2(int A[], int n) {
for (int i=0; i<n; i++)
{
if (A[i] > 0 && A[i] < n)
{
//if (A[i]-1 != i && A[A[i]-1] != A[i])不用那么多条件就可以了。
//因为只要是已经到位了的元素即：A[i]-1==i了，那么判断如果有重复元素
//两个位置交换就最好考虑好两个位置出现的可能情况。考虑问题全面，两个条件都考虑好。
//update:增加i!=A[i]表示i位置没到位，A[A[i]-1] != A[i]表示A[i]-1位置没到位，两个位置都判断也很好的。
if (A[A[i]-1] != A[i])
{
swap(A[A[i]-1], A[i]);
i--;
}
}
}
for (int j=0; j<n; ++j)
if (A[j]-1 != j)
return j+1;
return n+1;
}
也是思路二，不过上面的是处理下标从1开始，下面的程序是处理下标从0开始的：
int firstMissingPositive3(int A[], int n) {
int i = 0;
while (i < n) {
//逐个把A[i]放到A[i]位置的思想
//1：找到一个A[i]是在0到n范围的就放到相应位置
//2：没找到的直接跳过
//简单来说：就是把数字与下标对应起来
if (A[i] >= 0 && A[i] < n && A[A[i]] != A[i])
swap(A[i], A[A[i]]);
else i++;
}
int k = 1;
while (k < n && A[k] == k) k++;
if (n == 0 || k < n) return k;
else return A[0] == k ? k + 1 : k;
}
1 排序之后查找
2 把出现的数值放到与下标一致的位置，再判断什么位置最先出现不连续的数值，就是答案了。
3 和2差不多，把出现过的数值的下标位置做好标识，如果没有出现过的数组的下标就没有标识，那么这个就是答案。
int firstMissingPositive(int A[], int n) {
sort(A, A+n);
int res = 0;
int i = 0;
while (i<n && A[i]<=0) i++;
for (; i < n; i++)
{//注意：一看到序列就应该马上反应问题：是否有重复元素？？？
if (i>0 && A[i] == A[i-1]) continue;
if (A[i] - res != 1) return res+1;
else res = A[i];
}
return res+1;
}
X. https://discuss.leetcode.com/topic/12448/clear-java-solution/2public int firstMissingPositive(int[] nums) {
int start = 0;
int end = nums.length - 1;
while (start <= end) {
int index = nums[start] - 1;
if (index == start)
start++;
else if (index < 0 || index > end || nums[start] == nums[index])
nums[start] = nums[end--];
else {
nums[start] = nums[index];
nums[index] = index + 1;
}
}
return start + 1;
}http://blog.csdn.net/kenden23/article/details/17099987
Also refer to http://tianrunhe.wordpress.com/2012/07/15/finding-the-1st-missing-positive-int-in-an-array-first-missing-positive/
http://www.geeksforgeeks.org/find-the-smallest-positive-number-missing-from-an-unsorted-array/
Read full article from LeetCode - First Missing Positive | Darren's Blog
