k****t
发帖数: 184 | 1 If you have numbers in a 10,000 item array that range from 1 to 1 million,
and there is one duplicate. How do you find the duplicate with the simplest
algorithm?
我想到一种方法是从左到右，对每一个数字扫描其之后的数字。
另一种方法是用一个set，从左到右依次往set里面加，set.contains(...)来判断是否
是重复。
请问，有没有更好的方法？ |
b**********5
发帖数: 7881 | 2 use a bit vector? just less space
simplest
【在 k****t 的大作中提到】
: If you have numbers in a 10,000 item array that range from 1 to 1 million,
: and there is one duplicate. How do you find the duplicate with the simplest
: algorithm?
: 我想到一种方法是从左到右，对每一个数字扫描其之后的数字。
: 另一种方法是用一个set，从左到右依次往set里面加，set.contains(...)来判断是否
: 是重复。
: 请问，有没有更好的方法？
|
b*********e
发帖数: 26 | 3 第一种方法不成吧，set的大小才10,000，扫描worst case要1 million了
bit vector靠谱
用一个sizeof（int）就够了 |
k****t
发帖数: 184 | 4 能解释一下吗？sizeof(int)是指int字节长度？32？
还是max_int比如32767 ?
【在 b*********e 的大作中提到】
: 第一种方法不成吧，set的大小才10,000，扫描worst case要1 million了
: bit vector靠谱
: 用一个sizeof（int）就够了
|
b******i
发帖数: 914 | 5 1MN的数用Bit Vector得要128KB内存吧
【在 k****t 的大作中提到】
: 能解释一下吗？sizeof(int)是指int字节长度？32？
: 还是max_int比如32767 ?
|
