|
|---|
|
|
|
|
|
|
d*******y
发帖数: 31 | 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]) | d*****y
发帖数: 1365 | 2 1到n-1之间每个数至多被swap一次
n)
【在 d*******y 的大作中提到】
: 一个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])
| d*******y
发帖数: 31 | | p*****2
发帖数: 21240 | 4
n)
找一个就可以了呀？刚开始还以为要找所有的呢。
【在 d*******y 的大作中提到】
: 一个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])
| B********t
发帖数: 147 | 5 这不和找第一个missing positive差不多么。
case: 2 2 2 2 2. 这个程序能返回5么。。。
感觉应该swap了所有该swap的 最后再扫一遍吧
n)
【在 d*******y 的大作中提到】
: 一个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])
|
|
|
|
|
|
|
|
