b*****a
发帖数: 7 | 1 先贴题目：
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.
看到了两种做法，
第一种是取负数，
第二种是连续swap，然后比较A[i]和i+1。
很多人都使用第二种方法，但我对第二种方法有个疑问。
假如给了一个全是正整数的随机数列，用第二种方法可以得到一个排好序的数列，因为
是比较型的排序，时间复杂度应该是O(nlgn)吧？
请多多指教。刚开始找工作，觉得这里帮助很大。 | h*******8
发帖数: 29 | 2 问题是不能得到排好序的数组吧
比如[2,4,3] -> [4,2,3], 按照方法二的话。 | b*****a
发帖数: 7 | 3 我好像又想明白了，每一个数只会自己去找自己的值的地方一次，即使是被动交换的，
之后这个数也只会找一次，所以还是N次。 |
|
