最近在一次面试中,我被问到:
找到一个从第一个位置开始的未知长度的排序列表的中间元素。
我的回答如下:
有两个位置计数器:
counter1 counter2
将counter1增加1,将counter2增加2。当counter2达到列表的末尾时,counter1将位于中间。我认为这不是很有效,因为我会重复查看已经看过的节点。 无论如何,是否有更有效的算法?
最近在一次面试中,我被问到:
找到一个从第一个位置开始的未知长度的排序列表的中间元素。
我的回答如下:
有两个位置计数器:
counter1 counter2
将counter1增加1,将counter2增加2。当counter2达到列表的末尾时,counter1将位于中间。我认为这不是很有效,因为我会重复查看已经看过的节点。 无论如何,是否有更有效的算法?
3n/2
个节点,所以差别不大。假设您能够检测到已经超出了列表的末尾,并且能够有效地在列表中寻找任意位置,那么您可以不断将列表长度加倍(猜测长度为1,然后2,然后4,...),直到您超出了列表的末尾,然后使用二分查找在小于列表长度的最后一个尝试值和首个超过列表末尾的值之间找到实际的列表末尾。
然后,在位置END_OF_LIST / 2处查找。
这样,您就不必访问每个节点了。
// assume non-empty list
slow = fast = first;
count = 0;
while (fast)
{
fast = fast.next;
if (!fast)
break;
count++;
fast = fast.next;
if (fast)
count++;
slow = slow.next;
}
if (count % 2)
return slow.data;
else
return (slow.data + slow.next.data)/2.0;
从技术上讲,如果您使用链表,可以在一次遍历中使用O(N)内存来完成此操作。
编辑:我确实喜欢您的答案!
O(N)
,空间复杂度为O(1)
。这看起来相当不错。 - PengOne