P*******b
发帖数: 1001 | 1 A huge file contains unsorted integers. Find the median. The file cannot be
loaded in memory |
s*********t
发帖数: 1663 | 2 先外排序，然后再找median
be
【在 P*******b 的大作中提到】
: A huge file contains unsorted integers. Find the median. The file cannot be
: loaded in memory
|
b********e
发帖数: 693 | 3 extenal sort by using selection arg?
be
【在 P*******b 的大作中提到】
: A huge file contains unsorted integers. Find the median. The file cannot be
: loaded in memory
|
h**k
发帖数: 3368 | 4 如果文件中的整数分布均匀或者值域很小，buckets sort是个好方法。一般来说，只需
要读取文件两次，就可以找到。
be
【在 P*******b 的大作中提到】
: A huge file contains unsorted integers. Find the median. The file cannot be
: loaded in memory
|
x****k
发帖数: 2932 | 5 bucket sort to find the bucket holding median number, then generic sort or
heap or bucket sort again. |
x*****p
发帖数: 1707 | 6 1. Find max and min in O(n) time
2. Use binary search to find some x (may not be in the file), such that the
number of integers <= x is the same or 1 difference as the number of
integers >x. It takes O(nlogn) time.
3. Find the closes integer to x in the file. It takes O(n) time.
Totally O(nlogn), and the space required is O(1). |
P*******b
发帖数: 1001 | 7 这样找出来的不一定是ｍｅｄｉａｎ吧，只是个大约比较ｍｅｄｉａｎ的数吧。
the
【在 x*****p 的大作中提到】
: 1. Find max and min in O(n) time
: 2. Use binary search to find some x (may not be in the file), such that the
: number of integers <= x is the same or 1 difference as the number of
: integers >x. It takes O(nlogn) time.
: 3. Find the closes integer to x in the file. It takes O(n) time.
: Totally O(nlogn), and the space required is O(1).
|
h**6
发帖数: 4160 | 8 前面 bucket sort 的方法是对的，找出最大最小值，然后根据取值范围分成 256 或者 65536 个 bucket ，统计每个 bucket 内的元素个数，得出中位数再哪个 bucket 里面的第几个。如果该 bucket 内元素个数仍然过多，不能放入内存，那么就继续划分，否则可放入内存排序后得出答案。 |
