r*******g
发帖数: 1335 | 1 给定一个包含4300000000个32位整数的顺序文件，如何找一个至少出现2次得整数
有一道题是找没有出现的整数，而这道题是找重复出现两次的整数，都来自
programming pearls，这道题到底怎么弄，没看明白？
谢谢了 |
d*******d
发帖数: 2050 | 2 b search
【在 r*******g 的大作中提到】
: 给定一个包含4300000000个32位整数的顺序文件，如何找一个至少出现2次得整数
: 有一道题是找没有出现的整数，而这道题是找重复出现两次的整数，都来自
: programming pearls，这道题到底怎么弄，没看明白？
: 谢谢了
|
r*******g
发帖数: 1335 | 3 我晕
英文版的书上没有说是顺序文件，中文版的书说是顺序文件，如果非顺序而且内存有限
，怎么弄
given a tape containing 1050000 twenty-bit integers, how can you find one
that appears at least twice?
和中文版的书完全不同啊，貌似我看的不是一个版本。。。
【在 d*******d 的大作中提到】
: b search
|
d*******d
发帖数: 2050 | 4 真的是b search, 参考150题中某题。
【在 r*******g 的大作中提到】
: 给定一个包含4300000000个32位整数的顺序文件，如何找一个至少出现2次得整数
: 有一道题是找没有出现的整数，而这道题是找重复出现两次的整数，都来自
: programming pearls，这道题到底怎么弄，没看明白？
: 谢谢了
|
r*******g
发帖数: 1335 | 5 hi, 你们一般说的150是careercup top 150 questions,还是其他什么150？谢谢了。
如果未排序，也是binary search吗？
【在 d*******d 的大作中提到】
: 真的是b search, 参考150题中某题。
|
g**********y
发帖数: 14569 | 6 如果无序的数组，你怎么binary search?
【在 d*******d 的大作中提到】
: 真的是b search, 参考150题中某题。
|
d*******d
发帖数: 2050 | 7 对每一个bit计数,每次cut range in half, 数32次就可以了.
【在 g**********y 的大作中提到】
: 如果无序的数组，你怎么binary search?
|
g**********y
发帖数: 14569 | 8 哦，是我看错了，2^32比那个4300000000小。
【在 d*******d 的大作中提到】
: 对每一个bit计数,每次cut range in half, 数32次就可以了.
|
k****n
发帖数: 369 | 9 bitmap
【在 r*******g 的大作中提到】
: 给定一个包含4300000000个32位整数的顺序文件，如何找一个至少出现2次得整数
: 有一道题是找没有出现的整数，而这道题是找重复出现两次的整数，都来自
: programming pearls，这道题到底怎么弄，没看明白？
: 谢谢了
|
k****n
发帖数: 369 | 10 比如对最高位，看0有多少个，1有多少个
肯定有某一种多过一半，然后再看次高位
【在 r*******g 的大作中提到】
: hi, 你们一般说的150是careercup top 150 questions,还是其他什么150？谢谢了。
: 如果未排序，也是binary search吗？
|
|
|
r*******g
发帖数: 1335 | 11 Hi, bitmap 的话，难道不是需要43000000位的内存空间，貌似也挺大的。
【在 k****n 的大作中提到】
: bitmap
|
k****n
发帖数: 369 | 12 2^32 bit, 2^29 byte, that's only 512M
usually only a piece of cake for modern computers
【在 r*******g 的大作中提到】
: Hi, bitmap 的话，难道不是需要43000000位的内存空间，貌似也挺大的。
|
d*******d
发帖数: 2050 | 13 这题人家一般会故意为难你,告诉你只有100个byte.....
【在 k****n 的大作中提到】
: 2^32 bit, 2^29 byte, that's only 512M
: usually only a piece of cake for modern computers
|
k****n
发帖数: 369 | 14 then b search...
【在 d*******d 的大作中提到】
: 这题人家一般会故意为难你,告诉你只有100个byte.....
|
N*D
发帖数: 3641 | 15 这个靠谱
【在 d*******d 的大作中提到】
: 对每一个bit计数,每次cut range in half, 数32次就可以了.
|
r*******g
发帖数: 1335 | 16 这个和binary search什么关系，你们貌似说的两种方法，直接bitmap确实有内存问题。
你貌似在说，每次总是找多的那一半，对多的那一半，再拆分，再找，这样得到的数就
是重复的。貌似这样确实可以。这个是binary search？
我现在和找missing integer的方法搞混了，那个也是这样做，但是每次找少的一半，
而且找到一定程度了就直接对剩下的排序去找missing，不知道我理解对了没有
【在 k****n 的大作中提到】
: 比如对最高位，看0有多少个，1有多少个
: 肯定有某一种多过一半，然后再看次高位
|
k****n
发帖数: 369 | 17 每次去掉一半的范围，不就是binary search吗？
和missing integer的确是同样的道理
题。
【在 r*******g 的大作中提到】
: 这个和binary search什么关系，你们貌似说的两种方法，直接bitmap确实有内存问题。
: 你貌似在说，每次总是找多的那一半，对多的那一半，再拆分，再找，这样得到的数就
: 是重复的。貌似这样确实可以。这个是binary search？
: 我现在和找missing integer的方法搞混了，那个也是这样做，但是每次找少的一半，
: 而且找到一定程度了就直接对剩下的排序去找missing，不知道我理解对了没有
|
r*******g
发帖数: 1335 | 18 是哦
哈哈
我一想到binary search，就想到排序后进行查找。。。。
【在 k****n 的大作中提到】
: 每次去掉一半的范围，不就是binary search吗？
: 和missing integer的确是同样的道理
:
: 题。
|
a**********2
发帖数: 340 | 19 如果很多个数都出现超过两次，这样计数不是没有意义了吗？
内存不够还是需要外排序吧？
【在 d*******d 的大作中提到】
: 对每一个bit计数,每次cut range in half, 数32次就可以了.
|
