一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 479|回复: 19
收起左侧

[算法题] First Missing Positive

[复制链接] |试试Instant~ |关注本帖
love1point 发表于 2015-8-10 01:46:03 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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:58 | 显示全部楼层
  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
回复 支持 反对

使用道具 举报

354886 发表于 2015-8-10 07:06:25 | 显示全部楼层
lz可以去看一下计数排序
回复 支持 反对

使用道具 举报

EroicaCMCS 发表于 2015-8-10 08:19:06 | 显示全部楼层
基数排序:
  1. class Solution:
  2.     # @param {integer[]} nums
  3.     # @return {integer}
  4.     def firstMissingPositive(self, nums):
  5.         size = len(nums)

  6.         for i in xrange(size):
  7.             while nums[i] != i + 1:
  8.                 if nums[i] <= 0 or nums[i] > size or nums[i] == nums[nums[i] - 1]: break
  9.                 nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

  10.         for i in xrange(size):
  11.             if nums[i] != i + 1:
  12.                 return i + 1

  13.         return size + 1
复制代码
回复 支持 反对

使用道具 举报

zws0818 发表于 2015-8-10 09:42:37 | 显示全部楼层
无序数组的题目如果要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]时会陷入死循环。这种情况下直接跳过。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-10 09:53:22 | 显示全部楼层
post your solution. Let us help you check it.
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-8-10 09:54:45 | 显示全部楼层
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-10 09:56:41 | 显示全部楼层
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. }
复制代码
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-10 15:02:35 | 显示全部楼层
本帖最后由 hulahu 于 2015-8-10 15:06 编辑

帮你调出来的了

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

            int temp = nums;
            nums = nums[temp - 1];
            nums[temp-1] = temp;
            i--;
        }
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-8-11 22:36:04 | 显示全部楼层
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
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-12 01:20:27 | 显示全部楼层
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 + 1 || nums <= 0 || nums > nums.length || nums == nums[nums-1])
            {
                continue;
            }
            
            int temp = nums;
            nums = nums[temp - 1];
            nums[temp-1] = temp;
            i--;
        }
        
        for(int i = 0; i < nums.length; i++)
        {
            if(nums != i + 1)
            {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
}
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-8-12 01:47:28 | 显示全部楼层
hulahu 发表于 2015-8-12 01:20
你copy这个到leetcode, 看看能不能跑过。

public class Solution {

感想回复。
现在leetcode在维护中,等可以提交时我再提交。给你反馈哈。谢谢
回复 支持 反对

使用道具 举报

flyaway25 发表于 2015-8-12 02:05:29 | 显示全部楼层
love1point 发表于 2015-8-12 01:47
感想回复。
现在leetcode在维护中,等可以提交时我再提交。给你反馈哈。谢谢

你的code在交换那先改变了nums的值所以后面的式子中nums-1就不对了,后面nums[nums-1]里面的nums应该用的是改变之前的值。你可以试下先改变nums[nums-1]的值然后交换给nums
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-8-12 03:50:05 | 显示全部楼层
hulahu 发表于 2015-8-12 01:20
你copy这个到leetcode, 看看能不能跑过。

public class Solution {

非常感谢。你的代码可以过哈,只要nums 换成 nums, 我懂你意思哈
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-8-12 03:50:55 | 显示全部楼层
flyaway25 发表于 2015-8-12 02:05
你的code在交换那先改变了nums的值所以后面的式子中nums-1就不对了,后面nums[nums-1]里面的nums应该用的 ...

是的,你的一句话提醒梦中人,不然我老是改不出来。非常感谢
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-8-12 03:52:05 | 显示全部楼层
感谢各位的纠正。

可以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. }
复制代码
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-12 05:51:48 | 显示全部楼层
love1point 发表于 2015-8-12 03:52
感谢各位的纠正。

可以ac代码;

奇怪, 我之前copy 的怎么和我local 的不一样。难怪你喊跑不过。 怎么贴代码啊。
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-8-12 05:54:11 | 显示全部楼层
hulahu 发表于 2015-8-12 05:51
奇怪, 我之前copy 的怎么和我local 的不一样。难怪你喊跑不过。 怎么贴代码啊。

我改了你一点代码哈,所以我没过。你的基本正确哈。

点击这个 <>  贴代码哈   
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 13:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表