关注
问答题参考解法:
题目大意:给你一个ipv4地域库(ipv4地址的网段表示法,比如12.34.56.0/24,对应相应地理位置的表),保证各个网段互不重叠,但是一个地域可以对应多个网段。请设计一个数据结构,能过快速地查询用户询问的ip所对应的地理位置。请说明你的方法的时空复杂度。
参考解法:
计算机中ipv4地址是32位无符号整数。
我们将ipv4的地址和网段都变成32位无符号整数,然后转换成对应的32位的二进制表示。
之后使用字典树/键树/Trie(二叉树也可以),每个节点有2个分支:一个分支表示下一位是0,另一个分支表示下一位是1.
首先要将所有地域库的信息插入这个树中。对网段,保留相应的掩码长度,在掩码长度最后一位对应的节点,顺带标记上,这是一个网段节点,对应的地域为xxx。
插入完成之后,我们可以处理查询。对每个查询,转成32位的01串,在树上,根据每一位的具体值,决定往下走到哪个节点,来进行查找。当走到某个节点,走不下去的时候:
如果这个节点没有地域信息,说明库中没有对应条目。
如果这个节点有地域信息,说明我们找到了,返回这个地域信息。
综上所述:
插入阶段:
时间复杂度O(32n)=O(n)
空间复杂度O(32n)=O(n)
其中n为地址库中的地址数目
查询阶段:
时间复杂度O(32)=O(1)
空间复杂度O(1)
查看原帖
点赞 评论
相关推荐
![](https://static.nowcoder.com/fe/file/oss/1716965564844UEBJN.png)
![](https://static.nowcoder.com/fe/file/oss/1716965585666UBBME.png)
深信服
| 校招
| 14个岗位
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 面试被问“你的缺点是什么?”怎么答 #
5103次浏览 83人参与
# 租房找室友 #
7812次浏览 53人参与
# 水滴春招 #
14708次浏览 167人参与
# 25届秋招公司红黑榜 #
238056次浏览 988人参与
# 入职第四天,心情怎么样 #
10925次浏览 56人参与
# 简历无回复,你会继续海投还是优化再投? #
48508次浏览 560人参与
# 机械人选offer,最看重什么? #
69046次浏览 449人参与
# 牛友们的论文几号送审 #
15968次浏览 500人参与
# 软开人,你觉得应届生多少薪资才算合理? #
81328次浏览 496人参与
# 国企还是互联网,你怎么选? #
109087次浏览 852人参与
# 22届毕业,是读研还是拿外包offer先苟着 #
4636次浏览 27人参与
# 机械人,你的秋招第一份简历被谁挂了 #
125787次浏览 1925人参与
# 总结:哪家公司面试体验感最差 #
33250次浏览 169人参与
# 职场新人生存指南 #
198762次浏览 5495人参与
# 安利/避雷我的专业 #
62060次浏览 481人参与
# 读研or工作,哪个性价比更高? #
26016次浏览 356人参与
# 听劝,这个公司值得去吗 #
382261次浏览 1515人参与
# 参加完秋招的机械人,还参加春招吗? #
26661次浏览 275人参与
# 你觉得早上几点上班合适? #
61633次浏览 256人参与
# 如果重来一次你还会读研吗 #
155641次浏览 1705人参与
# 你们的毕业论文什么进度了 #
900308次浏览 8944人参与