📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 5378| 回复: 18
跳转到指定楼层
上一主题 下一主题
收起左侧

关于电话本存储的数据结构

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
我记得去年上数据结构课的时候捞印老师说过数据库的主要数据结构是字典树和Hashmap来着。。如果没记错的话。。= =

然后这两天刷题看到了一道题是问电话本应该用什么数据结构存储,然后好多小伙伴答是用Hashmap存。具体这道题有没有其他的附加条件不知道,如果仅仅是问一个小的电话本存储应该就是Hashmap来着~

然后我的问题是:如果电话本用Trie存储的话,缺点是不是仅仅只有空间复杂度比较大啊?或者有没有小伙伴给还原一下原题。。就是Bloomberg他家的面经中的一道题。。总觉得不应该是这么简单的问题噗。。

谢谢各路大神们~~~看到我看到我看到我~~~~

评分

参与人数 2大米 +6 收起 理由
bryanjhy + 3 给你点个赞!
yabay91 + 3 感谢分享!

查看全部评分


上一篇:小白求问CC150的答案为什么那么复杂。。。
下一篇:Reorder List求大神debug,实在不知道错在哪里
全局:
sherry900105 发表于 2015-1-15 22:58
唔。。为啥我感觉hashmap的空间复杂度是O(n),trie的best case是O(log(m*n)) worst case 是O(m*n)。。。 ...

n是单词个数?m是单词平均长度?
那hashmap也应该是O(mn)吧?你不能对trie用character来统计,但是对hashmap用string来算
回复

使用道具 举报

推荐
zcy1848 2015-1-16 01:46:48 | 只看该作者
全局:
觉得是Trie, 从空间复杂度的角度来说,trie可以省略存储重复字符,复杂度应该更小才对。还有更重要的一个问题是电话本要实现排序,用hashmap来存的话每次都都要排序,太浪费时间了吧。还有就是电话本的一个功能是输入几个字母,比如"t",可以显示以它打头的人名"tim", "tom",trie也可以实现这个功能。所以觉得还是trie更合适些
回复

使用道具 举报

🔗
yabay91 2015-1-15 11:45:54 | 只看该作者
全局:
同问。。。觉得应该是trie。。。。求各位大大给个解答
回复

使用道具 举报

🔗
 楼主| sherry900105 2015-1-15 12:11:40 | 只看该作者
全局:
yabay91 发表于 2015-1-15 11:45
同问。。。觉得应该是trie。。。。求各位大大给个解答

看到的所有答案都是hashmap呢。。其实我觉得貌似两个都可以 只是哪个好的问题吧==
回复

使用道具 举报

🔗
Adeath 2015-1-15 14:11:49 | 只看该作者
回复

使用道具 举报

🔗
 楼主| sherry900105 2015-1-15 22:25:54 | 只看该作者
全局:
Adeath 发表于 2015-1-15 14:11
BST  参见
http://www.programmerinterview.com/index.php/data-structures/hash-tables-versus-binary-se ...

喂喂。。不是BST啦。。是Trie啦。。= =又见你。。
回复

使用道具 举报

全局:
为什么我觉得trie的空间复杂度比hashmap低。。
回复

使用道具 举报

🔗
mayingjie116 2015-1-15 22:51:52 | 只看该作者
全局:
用Trie吧,还可以扩展一个字符串补全功能
回复

使用道具 举报

🔗
 楼主| sherry900105 2015-1-15 22:53:58 | 只看该作者
全局:
mayingjie116 发表于 2015-1-15 22:51
用Trie吧,还可以扩展一个字符串补全功能

0 0 可是地里一水的Hashmap。。。我也不知道为啥了。。
回复

使用道具 举报

🔗
 楼主| sherry900105 2015-1-15 22:58:28 | 只看该作者
全局:
圆梦梦剧场 发表于 2015-1-15 22:29
为什么我觉得trie的空间复杂度比hashmap低。。

唔。。为啥我感觉hashmap的空间复杂度是O(n),trie的best case是O(log(m*n)) worst case 是O(m*n)。。。怎么看都是hashmap优于Trie吧。。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表