题目描述:
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.
首先未出现的数的范围必是在[1,N],所以可以用一个N长的数组来做标记,但是这样是O(N)的空间,在网上看有大牛提出了利用原数组来做标记的办法,首先因为原来包含的0和负数都不会出现在[1,N]中,即对结果是没有贡献的,所以可以在预处理阶段将这些数置为一个很大的正数,然后扫描数组,遇到一个......
阅读全文