[去哪儿网] 6亿个IP地址的快速映射


给定一个200MB的文本文件,里面存的是IP地址到真实地址信息的映射信息,例如:211.200.101.100北京
然后给你6亿个IP地址,请设计算法快速的打印出所对应的真实地址信息。

我的第一个想法用tree树但不知道对不对加粗文字 也不知道这个问题的答案是什么 求说下思路
已邀请:

jefflee

赞同来自: Black lithium 天白才痴


考虑到ip地址分布的高度不均匀(国外地址段信息应该很少吧),开个高度为5的树好了。每个父节点有256个子节点。每个节点固定分配长度为256的int*.
空间复杂度: 最占空间的是叶子节点,不需要有256的int*,只需要一个指针(或者文件offset)指向ip地址描述。也就是一个int。所以是略大于4N字节。
查询的时间复杂度:4 + 读描述时间

要回复问题请先登录注册