这是一个创建于 4396 天前的主题，其中的信息可能已经有所发展或是发生改变。
从前有个国家，有1千万的子民，每个人都有一个唯一编码18位，随即生成的。
然后皇帝要建一个档案管理部门，让子民来存档案，取档案。
你是那部门负责人，部门里面有个机器，用来存数据的，机器里有5千万个箱子，每个箱子放一个信封，信封里是子民的信息，可以贴字条在信封上。
子民来只把唯一18位编码告诉工作人员，取的时候也是通过18位编码。
你要写手册给部门的工作人员，叫他们怎么把子民对应的信息的信封放到机器里。
如果做不出，皇帝砍你头。
然后皇帝要建一个档案管理部门，让子民来存档案，取档案。
你是那部门负责人，部门里面有个机器，用来存数据的，机器里有5千万个箱子，每个箱子放一个信封，信封里是子民的信息，可以贴字条在信封上。
子民来只把唯一18位编码告诉工作人员，取的时候也是通过18位编码。
你要写手册给部门的工作人员，叫他们怎么把子民对应的信息的信封放到机器里。
如果做不出，皇帝砍你头。
 |
1
pengjiayou 2012-11-08 12:35:34 +08:00
我是要被砍头的那位，我做不出，哈哈
|
 |
2
013231 2012-11-08 12:46:30 +08:00
這不就是散列表麼.
信封上貼上編號, 放在第`編碼%5千萬`個箱子裏; 如果那個箱子已經有一個信封了就往依次後看, 找到了空箱子就放進去. 取信的時候到`編碼%5千萬`個箱子去區; 如果不在那個箱子就往後找. |
 |
4
21grams 2012-11-08 14:16:11 +08:00
就按编码取呗，实在看不懂要干什么。
|
 |
6
gucheen 2012-11-08 14:19:51 +08:00
机器工作的原理貌似不知道。。。
|
1 |
9
y051313 2012-11-08 15:00:19 +08:00
题目不严谨吧，是说取的时候只能一次？也就是说不能再箱子里面翻来翻去？
|
 |
13
chendeshen 2012-11-08 20:14:46 +08:00
这题算是考数据结构,再套上一些故事情节而已.IOS考这个绝对是必要+出题出得好.
考得就是Hash(哈希表)的实现原理之一...答案貌似是 @013231 所说的±...本人小白路过... |
 |
14
blacktulip 2012-11-08 20:18:04 +08:00
话说虽然有5kw个箱子，我只用前1kw个不行么？
|
 |
15
ichigo 2012-11-08 20:35:47 +08:00
哈希表+1
|
|
16
013231 2012-11-08 21:08:22 +08:00
@blacktulip 這樣不大好. 只用前一千萬個, 想必你是準備按18位編碼順序存放, 然後二分搜索來查找位置?
這就有兩個問題: 1. 查找信封的速度是O(log n), 而散列表是O(1). 2. 一旦有新人加入, 平均需要移動五百萬個信封. |
 |
17
iYu 2012-11-08 21:25:02 +08:00
数组+1 编程珠玑 第一篇 O(1)
|
 |
18
soarscnu 2012-11-08 22:02:24 +08:00
把十八位编码和五千万个箱子各平均分为五部分，即一千万个箱子对应十八位编码的一部分。工作人员拿到十八位编码就到对应的部分第“十八位编码%1Kw”个箱子查找。若有多个信封对应一个箱子，则对应编号箱子放第一个对应的信封，再加一张字条，字条写明其它对应的信封放哪个编号箱子里。
|
 |
19
Veelian 2012-11-08 23:32:19 +08:00
大家是不是想太多了，人家说了「不会计算机的也有可能想出来」，逛超市存包时柜子吐出一个条形码。。。
|
 |
20
dhysum 2012-11-09 01:48:27 +08:00
最简单有效的应该还是树形结构
|
 |
21
yueq 2012-11-09 02:36:49 +08:00
this is hash bucket...
|
Select Language