LeetCode 41 - First Missing Positive


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
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.

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.

Since we only see each element at most twice as @makuiyu mentioned, the time complexity should be O(2n) = O(n). Sometimes we might see some negative numbers more than twice, but when that happens we will only see the positive number we swapped with that negative number once. In conclusion, it is equivalent we see all the positive number twice and negative number once. Let's assume k is the number of the positive numbers in the array, where k < n. The time complexity is O(2k + n - k) = O(n + k), where worst case is O(2n) = O(n).
what if the array has duplicates? Will this still work?
When it has duplicates, such as two 'x'. The first will be put into A[x-1]. And then the second 'x' will make 'A[x - 1] != x' false.

X. 解法一 交换
https://blog.csdn.net/haolexiao/article/details/53487436
还是用上面的解法，不过注意这道题有个tricky的地方在于nums[i]是换nums[nums[i]-1]还是换nums[nums[i]]
因为题目中要求找出缺失的第一个正整数，所以需要换nums[nums[i]-1]，因为这样保证如果1就应该出现在第一个位置，如果没有出现则说明缺少了1。如果题目中要求找出确实的第一个自然数（包括0）则需要换nums[nums[i]]；同理类比可得如果要找从2开始缺失的数，则需要换nums[nums[i]-2]

    int firstMissingPositive(vector<int>& nums) {
        for(int i=0;i<nums.size();i++){
            while(nums[i]>0 && nums[i]<=nums.size()&&nums[i] != nums[nums[i]-1])
                swap(nums[i],nums[nums[i]-1]);
        }

        for(int i=0;i<nums.size();i++)
            if(nums[i]!=i+1)
                return i+1;
        return nums.size()+1;
    }
This problem only considers positive numbers, so we need to shift 1 offset. The ith element is i+1.
http://bangbingsyb.blogspot.com/2014/11/leetcode-first-missing-positive.html
无序数组的题目如果要O(n)解法往往要用到hash table，但这题要求constant space。所以可以用数组本身作为一个"hash table"：A[0] = 1, A[1] = 2, .... A[n-1] = n。目标是尽可能将数字i放到数组第i-1个位置。

扫描数组中每个数：
1. 如果A[i]<1或者A[i]>n。说明A[i]一定不是first missing positive。跳过
2. 如果A[i] = i+1，说明A[i]已经在正确的位置，跳过
3. 如果A[i]!=i+1，且0<A[i]<=n，应当将A[i]放到A[A[i]-1]的位置，所以可以交换两数。
这里注意，当A[i] = A[A[i]-1]时会陷入死循环。这种情况下直接跳过
    int firstMissingPositive(int A[], int n) {
        int i=0;
        while(i<n) {
            if(A[i]!=i+1 && A[i]>0 && A[i]<=n && A[i]!=A[A[i]-1])
                swap(A[i],A[A[i]-1]);
            else
                i++;
        }
        for(int i=0; i<n; i++) {
            if(A[i]!=i+1) return i+1;
        }
        return n+1;
    }
http://www.cnblogs.com/grandyang/p/4395963.html
既然不能建立新的数组，那么我们只能覆盖原有数组，我们的思路是把1放在数组第一个位置nums[0]，2放在第二个位置nums[1]，即需要把nums[i]放在nums[nums[i] - 1]上，那么我们遍历整个数组，如果nums[i] != i + 1, 而nums[i]为整数且不大于n，另外nums[i]不等于nums[nums[i] - 1]的话，我们将两者位置调换，如果不满足上述条件直接跳过，最后我们再遍历一遍数组，如果对应位置上的数不正确则返回正确的数
https://leetcode.windliang.cc/leetCode-41-First-Missing-Positive.html
如果没限制空间复杂度，我们可以这样想。用一个等大的数组去顺序保存这些数字。
比如说，数组 nums [ 3 4 -1 1 8]，它的大小是 5。然后再创建一个等大的数组 a，初始化为 [ - 1，- 1，- 1，- 1，-1] 。然后我们遍历 nums，把数字分别存到对应的位置。1 就存到数组 a 的第 1 个位置（a [ 0 ]），2 就存到数组 a 的第 2 个位置（a [ 1 ]），3 就存到数组 a 的第 3 个位置（a [ 2 ]）...
nums [ 0 ] 等于 3，更新 a [ - 1，- 1，3，- 1，-1] 。
nums [ 1 ] 等于 4，更新 a [ - 1，- 1，3，4，-1 ] 。
nums [ 2 ] 等于 - 1，不是正数，忽略。
nums [ 3 ] 等于 1，更新 a [ 1，- 1，3，4，-1 ] 。
nums [ 4 ] 等于 8，我们的 a 数组只能存 1 到 5，所以同样忽略。
最后，我们只需要遍历 a 数组，遇到第一次 a [ i ] ！= i + 1，就说明缺失了 i + 1。因为我们的 a 数组每个位置都存着比下标大 1 的数。
当然，上边都是基于有一个额外空间讲的。如果没有额外空间，怎么办呢？
我们直接把原数组当成 a 数组去用。 这样的话，会出现的问题就是之前的数就会被覆盖掉。覆盖之前我们把它放回到当前数字的位置， 换句话说就是交换一下位置。然后把交换回来的数字放到应该在的位置，又交换回来的新数字继续判断，直到交换回来的数字小于 0，或者大于了数组的大小，或者它就是当前位置放的数字了。接着遍历 nums 的下一个数。具体看一下。
nums = [ 3 4 -1 1 8 ]
nums [ 0 ] 等于 3，把 3 放到第 3 个位置，并且把之前第 3 个位置的 -1 放回来，更新 nums [ -1， 4， 3， 1， 8 ]。
然后继续判断交换回来的数字，nums [ 0 ] 等于 -1，不是正数，忽略。
nums [ 1 ] 等于 4，把 4 放到第 4 个位置，并且把之前第 4个位置的 1 放回来，更新 nums [ -1， 1， 3， 4， 8 ]。
然后继续判断交换回来的数字，nums [ 1 ] 等于 1，把 1 放到第 1 个位置，并且把之前第 1 个位置的 -1 放回来，更新 nums [ 1， -1， 3， 4， 8 ]。
然后继续判断交换回来的数字，nums [ 1 ] 等于 -1，不是正数，忽略。
nums [ 2 ] 等于 3，刚好在第 3 个位置，不用管。
nums [ 3 ] 等于 4，刚好在第 4 个位置，不用管。
nums [ 4 ] 等于 8，我们的 nums 数组只能存 1 到 5，所以同样忽略。
最后，我们只需要遍历 nums 数组，遇到第一次 nums [ i ] ！= i + 1，就说明缺失了 i + 1。因为我们的 nums 数组每个位置都存着比下标大 1 的数。
看下代码吧，一个 for 循环，里边再 while 循环。
时间复杂度：for 循环里边套了个 while 循环，如果粗略的讲，那时间复杂度就是 O（n²）了。我们再从算法的逻辑上分析一下。因为每交换一次，就有一个数字放到了应该在的位置，只有 n 个数字，所以 while 里边的交换函数，最多执行 n 次。所以时间复杂度更精确的说，应该是 O（n）。
空间复杂度：O（1）。
public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    //遍历每个数字
    for (int i = 0; i < n; i++) {
        //判断交换回来的数字
        while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
            //第 nums[i] 个位置的下标是 nums[i] - 1
            swap(nums, i, nums[i] - 1);
        }
    }
    //找出第一个 nums[i] != i + 1 的位置
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    //如果之前的数都满足就返回 n + 1
    return n + 1;
}

https://leetcode.com/problems/first-missing-positive/discuss/17071/My-short-c%2B%2B-solution-O(1)-space-and-O(n)-time
Put each number in its right place.
For example:
When we find 5, then swap it with A[4].
At last, the first place where its number is not right, return the place + 1.
    int firstMissingPositive(int A[], int n)
    {
        for(int i = 0; i < n; ++ i)
            while(A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i])
                swap(A[i], A[A[i] - 1]);
        
        for(int i = 0; i < n; ++ i)
            if(A[i] != i + 1)
                return i + 1;
        
        return n + 1;
    }
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。最主要的区别就在于数组内数性质的变化，不再保证是基本连续的正整数了，其中可能会有负数和重复出现的数。但是利用桶排序的思路并没有变化，只是我们在做交换时需要更多的检查而已。类似于第一题中我们移动在数组中有位置的数，把N当做一个「锚」，在这里，我们把所有的负数、重复出现的数，以及在数组范围之外的数当做「锚」。

在这里，我们做了一点小处理，那就是把所有正整数在数组的位置都提前一位了，比如把5放在A[4]，这样可以让整体的逻辑更清晰一点儿，减少出错的机会。
此外，最容易出错的地方就是没有考虑重复数字出现的可能了。如果没有考虑到这一点，内层循环就会陷入到一个死循环当中。这一点也很好想，假设有一个数出现了两次，其中一个正好在它对应的位置上，当遍历到另外一个时，由于肯定与当前位置不符，就需要交换，而换回来的数就是还是它，这就导致了死循环。

int firstMissingPositive(vector<int> &A) {



int N = A.size();







for (int i = 0; i < N; ++i) {



while (A[i] > 0 && A[i] <= N && A[i] - 1 != i && A[i] != A[A[i] - 1])



swap(A[i], A[A[i] - 1]);



}







for (int i = 0; i < N; ++i)



if (A[i] != i + 1)



return i + 1;







return N + 1;



}
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.
  1. 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.
  2. 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.
  3. 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:
  1. Numbers greater then n can be ignored because the missing integer must be in the range 1..n+1
  2. 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. 

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);
}

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.
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/
  1. 如果A[i]不在自己该在的地方，就想办法把他换到该在的地方。如果A[i]是<=0或者A[i]比数组长度还大，说明没有它该在的地方，那就skip他，弄下一个（不用担心当前位置被它占了，如果后面有想在这个位置的正整数，它会被换走的）
  2. A[i]和A[A[i] – 1]换，然后继续回到i，接着换，直到第一种情况满足。但是如果这俩数一样，换也没用，就别原地打转了。
  3. 最后过一遍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.html
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
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/2
public 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
at
Labels: , , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts

  • Archives
  • LeetCode 471 - Encode String with Shortest Length
    Related:  LeetCode 394 - Decode String http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/ Given a  non...
  • Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks
    Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks Huffman coding is a lossless data compression algorithm. The idea is to assign ...
  • Buttercola: Buddy System
    Buttercola: Buddy System Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold: 1. A node...
  • Minimum area of a square enclosing given set of points
    Problem solving with programming: Minimum area of a square enclosing given set of points Given a set of coordinates in a two dimensional ...
  • HackerRank: N Puzzle
    HackerRank: N Puzzle N Puzzle is a sliding blocks game that takes place on a k * k grid with ((k * k) - 1) tiles each numbered from 1 to ...
  • LeetCode 394 - Decode String
    Follow up:  LeetCode 471 - Encode String with Shortest Length https://leetcode.com/problems/decode-string/ Given an encoded string, retu...
  • Hilbert Curve - Airbnb
    airbnb面试题汇总 Hilbert Curve Hilbert曲线可以无限阶下去，从1阶开始，落在一个矩阵里，让你写个function，三个参数（x,y,阶数），return 这个点（x,y）是在这阶curve里从原点出发的第几步 int hilbertCurve(...
  • Simple Text Editor - HackerRank
    https://www.hackerrank.com/challenges/simple-text-editor In this problem, your task is to implement a simple text editor. Initially, a fi...
  • LeetCode 291 - Word Pattern II
    leetcode 291 Word Pattern II Given a  pattern  and a string  str , find if  str  follows the same pattern. Here  follow  means a full m...