|
|
|
|
|
|
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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个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])
|
|
|
|
|
|
|