一个找duplicate element in an array的问题# JobHunting - 待字闺中
d*y
1 楼
一个array size n， element from 1 ~ n-1, 不确定有多少个duplicate，怎样用O(n)
的时间和 O（1）的空间来找出duplicate的元素。可以修改array
有人用这种code，这个是O（n）的复杂度吗？怎么分析呢？
for 1 <= i <= n:
while A[i] ≠ i:
if A[A[i]] = A[i]: return A[i]
swap(A[A[i]], A[i])
的时间和 O（1）的空间来找出duplicate的元素。可以修改array
有人用这种code，这个是O（n）的复杂度吗？怎么分析呢？
for 1 <= i <= n:
while A[i] ≠ i:
if A[A[i]] = A[i]: return A[i]
swap(A[A[i]], A[i])
