m********g
发帖数: 46 | 1 1M 7 digit phone numbers, 2MB spare memory, read each number only once and
sort them.
以前讨论过，但是没找到答案。
谢谢！ | v********w
发帖数: 136 | 2 notice the fact that no two phone number is the same, then map each phone
number into one bit. So for 7 digit phone number, one need 10^7 bit, which
is 10^7/8 Byte(< 2MB)
and
【在 m********g 的大作中提到】
: 1M 7 digit phone numbers, 2MB spare memory, read each number only once and
: sort them.
: 以前讨论过，但是没找到答案。
: 谢谢！
| m********g
发帖数: 46 | 3 You mean map a 7 digit phone number to a bit or map one digit of a phone
number to a bit? How can you map [0,1,...,9] to [0,1]? Thanks.
【在 v********w 的大作中提到】
: notice the fact that no two phone number is the same, then map each phone
: number into one bit. So for 7 digit phone number, one need 10^7 bit, which
: is 10^7/8 Byte(< 2MB)
:
: and
| s*********l
发帖数: 103 | 4
search bitmap (bit vector) or read the book "programming pearls"
【在 m********g 的大作中提到】
: You mean map a 7 digit phone number to a bit or map one digit of a phone
: number to a bit? How can you map [0,1,...,9] to [0,1]? Thanks.
| f*******r
发帖数: 198 | 5 you are not answering the question.
his question is how to map a number which could be larger than 1 to a bit,
but not a bit map.
I don't think the first answer is a right answer, tho i don't know the
answer either.
【在 s*********l 的大作中提到】
:
: search bitmap (bit vector) or read the book "programming pearls"
| s*********l
发帖数: 103 | 6
Well, the short answer is "use bitmap" and the OP can learn more by himself
starting from the hints I gave, either google or read the book I suggested.
If it is still not clear, hope the following pseudocode helps:
allocate 2MB memory filled by all 0's;
scan the list of phone numbers;
/*
treat the 2M memory block as a very long bit vector;
for i in numbers{ //assert(i<=9999999);
set the i-th bit of this bit vector to 1;
}
*/
scan the allocated memory bit by bit;
/* if the i-th bi
【在 f*******r 的大作中提到】
: you are not answering the question.
: his question is how to map a number which could be larger than 1 to a bit,
: but not a bit map.
: I don't think the first answer is a right answer, tho i don't know the
: answer either.
| f*******r
发帖数: 198 | 7 this is the right answer.
thank you very much.
himself
【在 s*********l 的大作中提到】
:
: Well, the short answer is "use bitmap" and the OP can learn more by himself
: starting from the hints I gave, either google or read the book I suggested.
: If it is still not clear, hope the following pseudocode helps:
: allocate 2MB memory filled by all 0's;
: scan the list of phone numbers;
: /*
: treat the 2M memory block as a very long bit vector;
: for i in numbers{ //assert(i<=9999999);
: set the i-th bit of this bit vector to 1;
| m********g
发帖数: 46 | |
|
