asp*_*100 4 algorithm data-structures
我有一个整数的排序列表,我希望在恒定时间内插入此列表中的任何元素.我被允许进行一些预处理,只要它能让我在恒定时间内运行这个操作(即,无论我在预处理后多少次重复此操作,它应该在恒定时间内运行).
如何才能做到这一点？
编辑:我可以想到一些更多的约束,使它不那么模糊,而且要解决起来更具挑战性 -
Zim*_*oot 5
您可以将整数放入基数树,将整数视为位串.如果基数为2且32位整数列表,则最大树深度为32,这是恒定时间插入的常数因素(通常不会做这样的事情,因为它的常数因素是基数树可能会大于平衡二叉树的对数因子,加上你需要为基数树做的所有比特都是昂贵的)
归档时间：
11 年，2 月 前
查看次数：
2778 次
最近记录：