美国人眼里的中国 老美也玩三国杀，吃老干妈！笑翻我鸟！ (转载)# Joke - 肚皮舞运动
b*a
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)吧？
请多多指教。刚开始找工作，觉得这里帮助很大。
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)吧？
请多多指教。刚开始找工作，觉得这里帮助很大。