First Missing Positive

I always cannot pass this problem. Does anyone who has the good algorithm to solve this problem?

https://leetcode.com/problems/first-missing-positive/

handsomecool 发表于 2015-8-10 06:47
没什么特别的，就是通过swap把数字放到应该在的位置，有点像sort colors

Thanks.

Your code can pass, but mine Java code cannot pass. Any advice?

1. public class Solution {
   
2.     public int firstMissingPositive(int[] nums) {
   
3.         if(nums == null || nums.length == 0)
   
4.         {
   
5.             return 1;
   
6.         }
   
7.         for(int i = 0; i < nums.length; i++)
   
8.         {
   
9.             if(nums[i] == i + 1 || nums[i] <= 0 || nums[i] > nums.length)
   
10.             {
    
11.                 continue;
    
12.             }
    
13.             
    
14.             int temp = nums[i];
    
15.             nums[i] = nums[nums[i] - 1];
    
16.             nums[nums[i] - 1] = temp;
    
17.         }
    
18.         
    
19.         for(int i = 0; i < nums.length; i++)
    
20.         {
    
21.             if(nums[i] != i + 1)
    
22.             {
    
23.                 return i + 1;
    
24.             }
    
25.         }
    
26.         return nums.length + 1;
    
27.     }
    
28. }
    

复制代码

love1point 发表于 2015-8-11 22:36
Thanks for reply.

But your code still cannot AC.

你copy这个到leetcode, 看看能不能跑过。

public class Solution {
    public int firstMissingPositive(int[] nums) {
        if(nums == null || nums.length == 0)
        {
            return 1;
        }
        for(int i = 0; i < nums.length; i++)
        {
            if(nums[i] == i + 1 || nums[i] <= 0 || nums[i] > nums.length || nums[i] == nums[nums[i]-1])
            {
                continue;
            }
            
            int temp = nums[i];
            nums[i] = nums[temp - 1];
            nums[temp-1] = temp;
            i--;
        }
        
        for(int i = 0; i < nums.length; i++)
        {
            if(nums[i] != i + 1)
            {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
}

感谢各位的纠正。

可以ac代码；

1. public class Solution {
   
2.     public int firstMissingPositive(int[] nums) {
   
3.         if(nums == null || nums.length == 0)
   
4.         {
   
5.             return 1;
   
6.         }
   
7.         for(int i = 0; i < nums.length; i++)
   
8.         {
   
9.             if(nums[i] == i + 1 || nums[i] <= 0 || nums[i] > nums.length || nums[i] == nums[nums[i]-1])
   
10.             {
    
11.                 continue;
    
12.             }
    
13.             
    
14.             int temp = nums[i];
    
15.             nums[i] = nums[nums[i] - 1];
    
16.             nums[temp-1] = temp;
    
17.             i--;
    
18.         }
    
19.         
    
20.         for(int i = 0; i < nums.length; i++)
    
21.         {
    
22.             if(nums[i] != i + 1)
    
23.             {
    
24.                 return i + 1;
    
25.             }
    
26.         }
    
27.         return nums.length + 1;
    
28.     }
    
29. }

复制代码

1. int firstMissingPositive(vector<int>& nums) {
   
2.         if(nums.size()==0) return 1;
   
3.         for(int i=0; i<nums.size(); i++){
   
4.             
   
5.             int val = nums[i];
   
6.             if(val==i+1||val<=0||val>nums.size()){
   
7.                 continue;
   
8.             }
   
9.             
   
10.             int tmp = nums[val-1];
    
11.             nums[val-1] = val;
    
12.             nums[i] = tmp;
    
13.             if(nums[val-1]!=nums[i])
    
14.                 i--;
    
15.             
    
16.         }
    
17.         
    
18.         for(int i=0;i<nums.size(); i++){
    
19.             if(nums[i]!=i+1) return i+1;
    
20.         }
    
21.         
    
22.         return nums.size()+1;
    
23.     }

复制代码

没什么特别的，就是通过swap把数字放到应该在的位置，有点像sort colors

lz可以去看一下计数排序

基数排序:

1. class Solution:
   
2.     # @param {integer[]} nums
   
3.     # @return {integer}
   
4.     def firstMissingPositive(self, nums):
   
5.         size = len(nums)
   
6. 
   
7.         for i in xrange(size):
   
8.             while nums[i] != i + 1:
   
9.                 if nums[i] <= 0 or nums[i] > size or nums[i] == nums[nums[i] - 1]: break
   
10.                 nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
    
11. 
    
12.         for i in xrange(size):
    
13.             if nums[i] != i + 1:
    
14.                 return i + 1
    
15. 
    
16.         return size + 1
    

复制代码

无序数组的题目如果要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]时会陷入死循环。这种情况下直接跳过。

post your solution. Let us help you check it.

hulahu 发表于 2015-8-10 09:53
post your solution. Let us help you check it.

Thanks.

1. public class Solution {
   
2.     public int firstMissingPositive(int[] nums) {
   
3.         if(nums == null || nums.length == 0)
   
4.         {
   
5.             return 1;
   
6.         }
   
7.         for(int i = 0; i < nums.length; i++)
   
8.         {
   
9.             if(nums[i] == i + 1 || nums[i] <= 0 || nums[i] > nums.length)
   
10.             {
    
11.                 continue;
    
12.             }
    
13.             
    
14.             int temp = nums[i];
    
15.             nums[i] = nums[nums[i] - 1];
    
16.             nums[nums[i] - 1] = temp;
    
17.         }
    
18.         
    
19.         for(int i = 0; i < nums.length; i++)
    
20.         {
    
21.             if(nums[i] != i + 1)
    
22.             {
    
23.                 return i + 1;
    
24.             }
    
25.         }
    
26.         return nums.length + 1;
    
27.     }
    
28. }
    

复制代码

love1point 发表于 2015-8-10 09:56
Thanks.

帮你调出来的了

for(int i = 0; i < nums.length; i++)
        {
            if(nums[i] == i + 1 || nums[i] <= 0 || nums[i] > nums.length || nums[i] == nums[nums[i]-1])
            {
                continue;
            }

            int temp = nums[i];
            nums[i] = nums[temp - 1];
            nums[temp-1] = temp;
            i--;
        }

hulahu 发表于 2015-8-10 15:02
帮你调出来的了

for(int i = 0; i < nums.length; i++)

Thanks for reply.

But your code still cannot AC.

if i = 0, if you i--, this will result in i = -1