计划高效率的多次对查找算法,要求时间为O(1)?

范子逸 2018-08-12 114 查找算法 空间复杂度 算法
有一堆数对,格式如下: <1, 3> <4-18, 9> <20, 123> <27, 156> <30-255, 189> ... 对,左边的数可能是个范围,如何设计查询算法使得通过左边的值查找到右边的值,比如20,找到123,15找到9,因为15在4-18范围内。 要求:时间复杂度尽可能低,不准申请额外的空间复杂度,比如用C++中的map存储,那么时间复杂度为O(nlogn),空间复杂度为O(1),有没有更好的方法呢? ---------------------------- 更新:可能说的不清楚,本来这些数…
其他回答
int[] table = new int[256];
table[1] = 3
table[4] = 9
table[5] = 9
table[6] = 9
...
table[255] = 189

差不多就是这样

算法里面的一个重要哲学就是空间换时间,时间换空间,又要马儿跑得快,又要马儿不吃草这种事情是基本上不存在的。
热心网民 2018-08-12 17:16:43 0条评论
worst case还要O(1),只能用数组了,左边当下标。
vczh 2018-08-12 17:16:43 0条评论
相关问答