一道面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道面试题

一道面试题# JobHunting - 待字闺中

g*e2010-08-16 07:08

1 楼

0-99 个数存在array里，如何找到重复的。回答建一个array记录下出现的次数，
>1的为重复的。再问如果不能有额外的空间，用何方法？回答用heap,但是用heap作
sort时是O(nlogn), 不够快。提示用一个swap，最后结果会是O(2n)。这个没回答
出, 请各位指教

f*52010-08-16 07:08

2 楼

问题是1..99 放在array[100]吧?

【在 g******e 的大作中提到】

: 0-99 个数存在array里，如何找到重复的。回答建一个array记录下出现的次数，
: >1的为重复的。再问如果不能有额外的空间，用何方法？回答用heap,但是用heap作
: sort时是O(nlogn), 不够快。提示用一个swap，最后结果会是O(2n)。这个没回答
: 出, 请各位指教

z*92010-08-16 07:08

3 楼

what are the numbers? are they in the range of 0-99?

g*e2010-08-16 07:08

4 楼

You are right.

【在 f*********5 的大作中提到】

: 问题是1..99 放在array[100]吧?

f*y2010-08-16 07:08

5 楼

问题是有可能有几个重复的，如果是一个重复的，全部加起来，减99*100/2最快了

c*e2010-08-16 07:08

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*e2010-08-16 07:08

7 楼

The method should be able to find any duplication.
For example, x[0]=...x[99].

【在 f*****y 的大作中提到】

: 问题是有可能有几个重复的，如果是一个重复的，全部加起来，减99*100/2最快了

K*g2010-08-16 07:08

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*A2010-08-16 07:08

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*u2010-08-16 07:08

10 楼

good, I thought out the same method.

【在 c**********e 的大作中提到】

c*e2010-08-16 07:08

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 的大作中提到】

y*m2010-08-16 07:08

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*e2010-08-16 07:08

13 楼

Doesn't 递归 cost memory?

【在 y***m 的大作中提到】

: 递归找岂不更省事？ n?..
:
: i=
: the

y*m2010-08-16 07:08

14 楼

cost? 进栈出栈吧
a1->5就 a5->5把老a5拿出，重复上一过程而已...

【在 c**********e 的大作中提到】

: Doesn't 递归 cost memory?