美文网首页
刷Lintcode:丢失第一个正整数

刷Lintcode:丢失第一个正整数

作者: 2a25936eedd9 | 来源:发表于2017-01-07 12:19 被阅读0次

    中等题

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

    样例

    如果给出[1,2,0], return3

    如果给出[3,4,-1,1], return2

      这道题算是中等题里面比较简单的,我的想法是构造一个数组B,它比A多出一个元素0,其余值与A相同。

    再对B排序,找出符合下列条件的值:

    B[i] >= 0; B[i+1] - B[i] > 1;

    然后返回B[i]+1。以下是我的代码。

    反观九章的答案,他没有另外构造数组,而是直接对A本身做了一些事情。这样节省了空间。时间复杂度上都是类似的。

    算法分析:

    相关文章

      网友评论

          本文标题:刷Lintcode:丢失第一个正整数

          本文链接:https://www.haomeiwen.com/subject/twkfbttx.html