标签:最优算法

判断单链表是否有环、求环长和环入口最优算法

判断单链表是否有环是一个十分经典的算法问题,许多考试或者面试都有很大的几率出现。如果事先对此没有一定的理解,临场发挥可能就比较困难了。   判断链表是否有环 首先定义两个指针 slow 和 fast,初始都指向链表头指针 head; 然后,slow 每走一步(每次移动一个节点),fast 走两步(移动两个节点); 如果 fast 遇到了 NULL……

查找单链表中倒数第k个节点的最优算法

假设单链表只给出头指针,长度为 n,在不改变链表的前提下,查找链表中倒数第 k 个位置上的结点。要求设计尽可能高效的算法(最优算法),并分析时间复杂度和空间复杂度。 最优算法的基本设计思想 定义两个指针变量 p 和 q,初始时均指向第一个结点; 然后 p 随着链表移动; 当 p 指针移动到第 k 个结点时,q 指针开始与 p 指针同步移动,也就是 p 移动……

求两个升序序列的中位数的最优算法

设计一个在时间和空间两方面都尽可能高效的算法,找出两个升序序列 A 和 B 的中位数(也就是两个序列合起来的中位数),最优算法思想如下: 设 A、B 的长度为 n,中位数分别为 a、b; 1)若 a=b,则 a 或 b 即为所求中位数,算法结束; 2)若 a<b,则舍弃 A 中较小的一半,同时舍弃序列 B 中较大的一半,要求两次舍弃的长度相等;   ……