41. First Missing Positive

Solution idea

1. 重要观察: for any array whose length is n, the smallest missing positive must be in range [1,...,n+1], so we only have to care about those elements in this range and remove the rest.
   • 例如：i=0放1，i=1放2，i=2放3，i=3放4，...，i=9放10。
2. 实现上:
   • STEP 1: '众神归位' - i位上对应的元素nums[i]，根据它的值，应该swap到nums[i]-1的index位上 (注意! 只有目标位置还没有被占时swap，如果已经有了，则跳过)
   • STEP 2: 再遍历一遍数组，找到第一个nums[i] != i+1的位置，返回i+1即可。找不到，最小的missing positive就是n+1。

Time complexity = $O(n)$

Resource

Golang concise solution with some explanation