Lintcode189 First Missing Positive solution 题解
发布在lintcode2018年1月27日view:223
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Given an unsorted integer array, find the first missing positive integer.

给出一个无序的整数数组,找出其中没有出现的最小正整数。

【题目链接】

www.lintcode.com/en/problem/first-missing-positive/

【题目解析】

此题可用桶排序。桶排序通常需要按照一定规则将值放入桶中,一般需要额外的 O(n) 空间,咋看一下似乎不太适合在这道题中使用,但是若能设定一定的规则原地交换原数组的值呢?这道题的难点就在于这种规则的设定。

设想我们对给定数组使用桶排序的思想排序,第一个桶放1,第二个桶放2,如果找不到相应的数,则相应的桶的值不变(可能为负值,也可能为其他值)。

那么怎么才能做到原地排序呢?即若 A[i]=x, 则将 x 放到它该去的地方 - A[x−1]=x, 同时将原来 A[x−1] 地方的值交换给 A[i].

排好序后遍历桶,如果不满足 f[i]=i+1, 那么警察叔叔就是它了!如果都满足条件怎么办?那就返回给定数组大小再加1呗。

【参考答案】

www.jiuzhang.com/solutions/first-missing-positive/

作者:程风破浪会有时 链接:https://www.jianshu.com/p/6394bfb710d3 來源:简书 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN
lintcode

lintcode题解

我的收藏