首页 > ACM题库 > LeetCode > LeetCode-First Missing Positive[排序]
2014
11-19

LeetCode-First Missing Positive[排序]

First Missing Positive

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

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

标签: Array
分析

本质上是桶排序(bucket sort),每当{A[i]!= i+1}的时候,将A[i]与A[A[i]-1]交换,直到无法交换为止,终止条件是 {A[i]== A[A[i]-1]}。

代码1

// LeetCode, First Missing Positive
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        bucket_sort(A, n);
        
        for (int i = 0; i < n; ++i)
            if (A[i] != (i + 1))
                return i + 1;
        return n + 1;
    }
private:
    static void bucket_sort(int A[], int n) {
        for (int i = 0; i < n; i++) {
            while (A[i] != i + 1) {
                if (A[i] <= 0 || A[i] > n || A[i] == A[A[i] - 1])
                    break;
                swap(A[i], A[A[i] - 1]);
            }
        }
    }
};

  1. Pingback: bondage straps

  2. Pingback: robert

  3. Pingback: pc games for windows 7

  4. Pingback: pc apps for windows 8

  5. Pingback: how to last longer

  6. Pingback: end of lease clean Melbourne

  7. Pingback: Sripatum university

  8. Pingback: sex toys lubricant

  9. Pingback: adam and eve sex toys

  10. Pingback: Best Sex Lubricant

  11. Pingback: Bondage Gear

  12. Pingback: Super Head Honcho Masturbator

  13. Pingback: Blue Dolphin Sex Toy

  14. Pingback: Clit Sensitizer

  15. Pingback: Magic Massager Deluxe

  16. Pingback: adam and eve

  17. Pingback: traditional vibrator

  18. Pingback: g spot

  19. Pingback: kala jadu

  20. Pingback: bandiere

  21. Pingback: rental bond cleaning Melbourne

  22. Pingback: adam and eve sex toy shop

  23. Pingback: vibrator pink

  24. Pingback: Bath Bombs

  25. Pingback: suction cup dildo

  26. Pingback: anal butt plug

  27. Pingback: best vibrator

  28. Pingback: butt plug

  29. Pingback: butt plug

  30. Pingback: gay toys

  31. Pingback: vibrating butt plug

  32. Pingback: Healthy food easy to prepare

  33. Pingback: g spot

  34. Pingback: label tudung

  35. Pingback: brush cutter,head line

  36. Pingback: vacuuming

  37. Pingback: adam and eve

  38. Pingback: what is the importance of sex

  39. Pingback: app download for windows 10

  40. Pingback: read more

  41. Pingback: gold vibrator

  42. Pingback: I Love News Paper

  43. Pingback: Taoist Real Sex Talk

  44. Pingback: real feel dildos

  45. Pingback: best butt plug

  46. Pingback: bangal ka jadu

  47. Pingback: rabbit vibrator

  48. Pingback: Venture Point Network

  49. Pingback: web design company

  50. Pingback: rampant vibrator

  51. Pingback: COB led luminaries

  52. Pingback: Duvet covers

  53. Pingback: small glass jars

  54. Pingback: basement remodeling in Atlanta

  55. Pingback: scr3888

  56. Pingback: free games download for pc

  57. Pingback: foreplay sex toys

  58. Pingback: triple vibrator

  59. Pingback: luxury sex toys

  60. Pingback: realistic vibrator

  61. Pingback: womens sex toy

  62. Pingback: best realistic dildo

  63. Pingback: honey usa

  64. Pingback: Jewelry

  65. Pingback: download tama tube

  66. Pingback: tratamento Alcoolismo

  67. Pingback: buy 100% kona

  68. Pingback: buy 100% kona

  69. Pingback: Rajamangala University of Technology Thanyaburi

  70. Pingback: coffee’s best kona

  71. Pingback: suction cup vibrating dildo

  72. Pingback: ean code

  73. Pingback: 2H2D

  74. Pingback: pink rabbit sex toy

  75. Pingback: sex toys for clit

  76. Pingback: adam eve toys

  77. Pingback: discount sex toys

  78. Pingback: sex toys cleaner

  79. Pingback: hands free sex toys

  80. Pingback: sex toys for couples

  81. Pingback: g-spot vibrators

  82. Pingback: how can i make money online

  83. Pingback: snuff bottles

  84. Pingback: unique antiques

  85. Pingback: leginy

  86. Pingback: kala jadoo

  87. Pingback: foldable wall bed

  88. Pingback: lefkoşa satılık daire fiyatları

  89. Pingback: Make Money Online

  90. Pingback: robert

  91. Pingback: barcode kaufen

  92. Pingback: uk email lists

  93. Pingback: Herbal Oils

  94. Pingback: tratamento de drogas

  95. Pingback: Double Sided Dildo

  96. Pingback: work home opportunities

  97. Pingback: masturbation

  98. Pingback: everyday deals trademark

  99. 歇歇吧。在美国的,天天都是美剧。F**k your mom 这话真很奇特。就是中国人的jargon。Wolf of Wall Street里面还有Dallas Buyer Club里面原话都是Mother F**ker.

  100. Pingback: pure kona

  101. Pingback: buy kona

  102. Pingback: Google

  103. Pingback: Google

  104. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  105. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  106. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  107. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  108. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  109. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。