g******e
发帖数: 247 | 1 0-99 个数存在array里，如何找到重复的。 回答建一个array记录下出现的次数，
>1的为重复的。再问如果不能有额外的空间，用何方法？回答用heap,但是用heap作
sort时是O(nlogn), 不够快。提示用一个swap，最后结果会是O(2n)。 这个没回答
出, 请各位指教 |
f*********5
发帖数: 576 | 2 问题是1..99 放在array[100]吧?
【在 g******e 的大作中提到】
: 0-99 个数存在array里，如何找到重复的。 回答建一个array记录下出现的次数，
: >1的为重复的。再问如果不能有额外的空间，用何方法？回答用heap,但是用heap作
: sort时是O(nlogn), 不够快。提示用一个swap，最后结果会是O(2n)。 这个没回答
: 出, 请各位指教
|
z***9
发帖数: 696 | 3 what are the numbers? are they in the range of 0-99? |
g******e
发帖数: 247 | 4
You are right.
【在 f*********5 的大作中提到】
: 问题是1..99 放在array[100]吧?
|
f*****y
发帖数: 444 | 5 问题是有可能有几个重复的，如果是一个重复的，全部加起来，减99*100/2最快了 |
c**********e
发帖数: 2007 | 6 two loops
for each i=0,..,99 (outerloop)
if i!=a[i] but a[i]==a[a[i]] then done.
else swap a[i] and a[a[i]] while a[i]!=i. (inner loop)
move to next i.
If there is a dup, it should be caught. |
c**********e
发帖数: 2007 | 7 The method should be able to find any duplication.
For example, x[0]=...x[99].
【在 f*****y 的大作中提到】
: 问题是有可能有几个重复的，如果是一个重复的，全部加起来，减99*100/2最快了
|
K******g
发帖数: 1870 | 8 能解释一下么？看不懂
【在 c**********e 的大作中提到】
: two loops
: for each i=0,..,99 (outerloop)
: if i!=a[i] but a[i]==a[a[i]] then done.
: else swap a[i] and a[a[i]] while a[i]!=i. (inner loop)
: move to next i.
: If there is a dup, it should be caught.
|
I**A
发帖数: 2345 | 9 that is to say
put 1 to 1st position. 2 to 2nd position and so on, by swaping.
suppose you are going to put a 9 into 9th position, but you find in 9th
position, it already has a 9 in it, then you know that 9 has duplicates
【在 K******g 的大作中提到】
: 能解释一下么？看不懂
|
p*u
发帖数: 136 | 10 good, I thought out the same method.
【在 c**********e 的大作中提到】
: two loops
: for each i=0,..,99 (outerloop)
: if i!=a[i] but a[i]==a[a[i]] then done.
: else swap a[i] and a[a[i]] while a[i]!=i. (inner loop)
: move to next i.
: If there is a dup, it should be caught.
|
|
|
c**********e
发帖数: 2007 | 11 for(int i=0;i<100;i++) {
while(a[i]!=i) {
if(a[i]==a[a[i]]) { cout << "find dublicate"; return; }
else { int j=a[i]; a[i]=a[j]; a[j]=j; }
}
}
Each i is visited at most twice. For example, if a[0]=5, after a swap
happens at i=0, a[5]=5. Then a[5] will not be visited for i=1,2,3,4. When i=
5, as a[5]==5 is true, the while loop will not run. So a[5] is visited at
most twice (it is likely return happens at i=3). So is each other i. So the
complexity is 2n.
【在 c**********e 的大作中提到】
: two loops
: for each i=0,..,99 (outerloop)
: if i!=a[i] but a[i]==a[a[i]] then done.
: else swap a[i] and a[a[i]] while a[i]!=i. (inner loop)
: move to next i.
: If there is a dup, it should be caught.
|
y***m
发帖数: 7027 | 12 递归找岂不更省事？ n?..
i=
the
【在 c**********e 的大作中提到】
: for(int i=0;i<100;i++) {
: while(a[i]!=i) {
: if(a[i]==a[a[i]]) { cout << "find dublicate"; return; }
: else { int j=a[i]; a[i]=a[j]; a[j]=j; }
: }
: }
: Each i is visited at most twice. For example, if a[0]=5, after a swap
: happens at i=0, a[5]=5. Then a[5] will not be visited for i=1,2,3,4. When i=
: 5, as a[5]==5 is true, the while loop will not run. So a[5] is visited at
: most twice (it is likely return happens at i=3). So is each other i. So the
|
c**********e
发帖数: 2007 | 13 Doesn't 递归 cost memory?
【在 y***m 的大作中提到】
: 递归找岂不更省事？ n?..
:
: i=
: the
|
y***m
发帖数: 7027 | 14 cost? 进栈出栈吧
a1->5就 a5->5把老a5拿出，重复上一过程而已...
【在 c**********e 的大作中提到】
: Doesn't 递归 cost memory?
|
c********g
发帖数: 449 | 15 {dup=5050-(a[0]+.....+a[99])} |
y*********e
发帖数: 518 | 16 不用额外空间，数组的每一个值又是在[0,100]区间的，用radix sort就可以了，
用O(n)的时间。sort好了之后再遍历一遍，就可以找到duplicate咯。
【在 g******e 的大作中提到】
: 0-99 个数存在array里，如何找到重复的。 回答建一个array记录下出现的次数，
: >1的为重复的。再问如果不能有额外的空间，用何方法？回答用heap,但是用heap作
: sort时是O(nlogn), 不够快。提示用一个swap，最后结果会是O(2n)。 这个没回答
: 出, 请各位指教
|
