M*S
发帖数: 459 | 1 Given an array t[100] which contains numbers between 1 and 99. Return the
duplicated value. Try both O(n) and O(n-square). Any idea how to do it?
Thanks a lot. |
w***g
发帖数: 5958 | 2 全都加起来，然后减去(1+99)*99/2。
【在 M*S 的大作中提到】
: Given an array t[100] which contains numbers between 1 and 99. Return the
: duplicated value. Try both O(n) and O(n-square). Any idea how to do it?
: Thanks a lot.
|
M*S
发帖数: 459 | 3 This is O(n^2). I guess we might use hash table to find out the duplicated
number with O(n). Not sure if there is any other smart way to do it.
【在 w***g 的大作中提到】
: 全都加起来，然后减去(1+99)*99/2。
|
p*u
发帖数: 2454 | 4 这种文物级的问题还要问啊，另外用一个array b[100]，initialize to -1。
if (b[a[i]] = -1) b[a[i]] = 1;
else cout << a[i] << "duplicate" << endl;
这个array就是一个特殊的hash table。
【在 M*S 的大作中提到】
: This is O(n^2). I guess we might use hash table to find out the duplicated
: number with O(n). Not sure if there is any other smart way to do it.
|
c*****t
发帖数: 1879 | 5 weak, add 或者 xor 不需要 extra space.
【在 p*u 的大作中提到】
: 这种文物级的问题还要问啊，另外用一个array b[100]，initialize to -1。
: if (b[a[i]] = -1) b[a[i]] = 1;
: else cout << a[i] << "duplicate" << endl;
: 这个array就是一个特殊的hash table。
|
v******n
发帖数: 421 | 6 where's n in your input...
【在 M*S 的大作中提到】
: Given an array t[100] which contains numbers between 1 and 99. Return the
: duplicated value. Try both O(n) and O(n-square). Any idea how to do it?
: Thanks a lot.
|
p*u
发帖数: 2454 | 7 人家没说只有一个duplicate吧，也不知道谁weak
【在 c*****t 的大作中提到】
: weak, add 或者 xor 不需要 extra space.
|
c*****t
发帖数: 1879 | 8 the duplicate value :)
【在 p*u 的大作中提到】
: 人家没说只有一个duplicate吧，也不知道谁weak
|
