题解 | #缺失的第一个正整数#

缺失的第一个正整数

http://www.nowcoder.com/practice/50ec6a5b0e4e45348544348278cdcee5

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int minNumberDisappeared(vector<int>& nums) {
        int n = nums.size();
        for(int i=0; i<nums.size(); i++){
            while(nums[i]>0 && nums[i] <=n && nums[i] != nums[nums[i]-1]){
                swap(nums[i], nums[nums[i]-1]);
            }
        }
        for(int i=0; i<n; i++){
            if(nums[i] != i+1)
                return i+1;
        }
        return n+1;
        // write code here
    }
};

(数组,哈希表,原地交换)

如果没有空间限制的话,可以使用哈希表来解,先把所有元素放入哈希表 set 中,然后从 1 开始在哈希表中查询第一个未出现的正整数。

要求使用常数空间的话想到在原数组原地交换,而我们关心的是正数,所以如果 nums[i] 是正数 > 0 且 < n 且 nums[i] 的位置上不是当前数,就把他放到应该的位置上去(防止死循环,如果原来就在正确的位置上,一直交换)

每个正数 nums[i] 的位置在 nums[i] - 1 上,即 0 的位置上放 1,以此类推(因为数组的大小是 n,那如果出现 n 放在位置 n 上会越界)。

最后再遍历一遍数组,如果当前位置上的数 nums[i] 不等于 i + 1,则 i + 1 就是缺少的正整数。

如果遍历结束之后,还没有找到答案,说明所有数都在正确的位置上,是一个连续序列,那么答案就是 n + 1。



全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
牛客刘北:如果暑期实习是27届的话,你要晚一年才会毕业,企业为什么会等你呢?要搞清时间逻辑呀!27届现在实习只能是在暑假实习,这是日常实习,不是暑期实习。所以多去投日常实习吧,暑期实习肯定不会要你的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务