在最近的一次采访中,我被问到:
从第一个位置开始查找未知长度的排序列表的中间元素.
我回答这个问题:
有2个位置计数器:
counter1 counter2
将counter1递增1,将counter2递增2.当计数器2到达列表的末尾时,计数器1将位于中间.我觉得这样做效率不高,因为我正在重新审视我已经看过的节点.无论哪种方式,是否有更高效的算法？
假设有一个链表,你可以在访问N个项目的同时访问它.
做5/4 N:
当你点击列表的末尾时,前一个锚点在中点之前,但至少已经有一半.所以N为完整迭代+最多1/4 N为锚= 5/4 N.
更频繁地丢弃锚点,例如在第1.5项的每个上限功率下,根据需要使您接近N(以跟踪更多锚点为代价;但对于任何给定的X作为功率步长,渐近记忆是恒定的) .