您当前的位置:首页 > 学习 > 阅览室

趣题:在双向有序链表中查找指定的数

时间:12-05来源:作者:点击数:

大家都知道,在一个有序数组里查找指定的数可以做到O(logn)的复杂度。但是大家想过没,在一个有序链表中又怎么样呢?让我们假设有这样一个链表,每个元素都严格小于它的后继元素。每个元素都能访问到自己的前驱元素和后继元素(如果有的话)。另外,我们知道每个元素在内存中的地址,因此可以进行随机存取。或者可以说,这个有序链表中的所有元素都是储存在一个数组中的,但数组本身并不有序。

现在,我们需要在这个链表中寻找一个指定的数x。你能否设计出一个平均复杂度低于O(n)的算法来?

下面是一个平均复杂度为O(√n)的算法。在数组中随机选取Θ(√n)个数,然后通过不断地比较更新,找出这些数当中比x小的最大的数(不妨记作p),以及比x大的最小的数(记作q)。从p所在的位置出发,沿着链表往下走,直到找到x或者走到q(表明x不在链表中)为止。

可以证明,O(√n)已经是最优的了。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门