一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2071|回复: 18
收起左侧

[算法题] 关于电话本存储的数据结构

[复制链接] |试试Instant~ |关注本帖
sherry900105 发表于 2015-1-15 11:37:09 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

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

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

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

评分

1

查看全部评分

圆梦梦剧场 发表于 2015-1-15 23:30:04 | 显示全部楼层
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来算
回复 支持 1 反对 0

使用道具 举报

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啦。。= =又见你。。
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2015-1-15 22:29:19 | 显示全部楼层
为什么我觉得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吧。。
回复 支持 反对

使用道具 举报

Adeath 发表于 2015-1-16 01:44:15 | 显示全部楼层
sherry900105 发表于 2015-1-15 22:25
喂喂。。不是BST啦。。是Trie啦。。= =又见你。。

你没仔细看 这篇文章就是讲电话本的数据结构的  
回复 支持 反对

使用道具 举报

头像被屏蔽
zcy1848 发表于 2015-1-16 01:46:48 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| sherry900105 发表于 2015-1-16 05:33:54 | 显示全部楼层
zcy1848 发表于 2015-1-16 01:46
觉得是Trie, 从空间复杂度的角度来说,trie可以省略存储重复字符,复杂度应该更小才对。还有更重要的一个问 ...

唔。。。谢谢回复啊!你这么一说貌似也对。。我只是记得当时老师讲的时候说Trie的空间复杂度要高一些来着。。。
回复 支持 反对

使用道具 举报

 楼主| sherry900105 发表于 2015-1-16 05:35:25 | 显示全部楼层
Adeath 发表于 2015-1-16 01:44
你没仔细看 这篇文章就是讲电话本的数据结构的

唔。。不好意思啊。。明天面试了。。所以急着赶着的一直在刷面经。。一会儿仔细看看~看到你说拿到Epic的offer了?你是什么时候毕业的啊?
回复 支持 反对

使用道具 举报

Adeath 发表于 2015-1-16 07:06:36 | 显示全部楼层
sherry900105 发表于 2015-1-16 05:35
唔。。不好意思啊。。明天面试了。。所以急着赶着的一直在刷面经。。一会儿仔细看看~看到你说拿到Epic的o ...

嗯  对电话本来讲hashmap最大的缺点就是unsorted  
下周答辩  就毕业了
回复 支持 反对

使用道具 举报

 楼主| sherry900105 发表于 2015-1-16 10:03:02 | 显示全部楼层
Adeath 发表于 2015-1-16 07:06
嗯  对电话本来讲hashmap最大的缺点就是unsorted  
下周答辩  就毕业了

那你找工作好快啊。。。我才刚开始一个多月。。还没有密集找呢。。不过你怎么这个时候毕业?是Phd?
回复 支持 反对

使用道具 举报

Adeath 发表于 2015-1-16 11:08:40 | 显示全部楼层
sherry900105 发表于 2015-1-16 10:03
那你找工作好快啊。。。我才刚开始一个多月。。还没有密集找呢。。不过你怎么这个时候毕业?是Phd?

嗯算比较快的 主要也是时间紧迫 不快不行啊…  我是春季入学的  1月来的  硕士
回复 支持 反对

使用道具 举报

 楼主| sherry900105 发表于 2015-1-16 11:50:07 | 显示全部楼层
Adeath 发表于 2015-1-16 11:08
嗯算比较快的 主要也是时间紧迫 不快不行啊…  我是春季入学的  1月来的  硕士

唔。。1月入学。。不是已经应该毕业了么。。所以觉得你是Phd。。= =
回复 支持 反对

使用道具 举报

Adeath 发表于 2015-1-16 12:14:45 | 显示全部楼层
sherry900105 发表于 2015-1-16 11:50
唔。。1月入学。。不是已经应该毕业了么。。所以觉得你是Phd。。= =

噢  我是那种做论文的硕士  课是早就上完了  论文稍微拖了一下  晚了一个月
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 13:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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