ITeye博客

lueye的博客

lueye · 共 6 篇文章

面试题:单链表O(1)时间复杂度内删除指定结点

给定头结点和指定结点,删除指定结点在时间复杂度为O(1) 思路:该节点的前驱无从着手,但后继容易获得。若该节点非末尾结点,则可以把后继结点复制给该节点。代码:node.data=node.next.data; node.next=node.next.next; 若该节点为末尾结点,即node.next==null时。需从头遍历,此时时间复杂度为O(N)。 综上时间复杂度为:(O(1)*(N-1)+O(N))/N=O(1)。 代码如下: package dataStructtion.linear; /** * 给定头结点和指定结点,删除指定结点在时间复杂度为O(1) * 思路:该节点的前驱无从…

2015-01-18 10:05 · 数据结构 · 评论(5)

面试题:找出单链表倒数第N个元素

第一种方法先求出元素个数,在遍历元素个数-n个,时间复杂度为:O(N+N-n)=O(2N-n)。 第二种设置俩个指针,第一个先走N步,第二个开始走。俩者速度一样,时间复杂度为O(N)。 代码如下: package dataStructtion.linear; /** * 获取单链表倒数第N个元素 * @author xiucai */ public class SingleLinkedList_LastN { /** * 第一种方法先求出元素个数,在遍历元素个数-n个 * 时间复杂度为:O(N+N-n)=O(2N-n) * @param list * @param n * @return *…

2015-01-18 09:28 · 数据结构 · 评论(1)

面试题:找出未知单链表中点元素

腾讯的面试题:找出未知单链表中点元素? 俩种方法: 第一种:全部遍历算出总长度为length;再遍历length/2个元素。时间复杂度为O(3N/2) 第二种:设置快慢指针。search速度为2,middle速度为1。当search完一遍时,middle正好 为中点元素。此时时间复杂度为O(N)。 其实还有第三种:若在单链表中设置len属性记录单链表长度,那么直接遍历N/2即可时间复杂 度为O(N/2)。 代码如下: package dataStructtion.linear; /** * 找出未知单链表中点元素 * @author xiucai */ public class Middle…

2015-01-18 08:36 · 数据结构 · 评论(0)

单链表的反转

算法和数据结构就是编程的一个重要部分,你若失掉了算法和数据结构,你就把一切都失掉了。尤其对于我等应届毕业生来说,能出得了手的也只有这些了。 对于校园招聘来说,互联网公司还是喜欢拿单链表的反转考验我们应届生的。话不多说,代码如下: package dataStructtion.linear; /** * 单链表的反转 * @author xiucai * */ public class SingleLinkedList_Reverse { public static <T> void reverse(SingleLinkedList<T> list){ Node<T> p=list.head.…

2015-01-17 20:09 · 数据结构 · 评论(0)

线性表的单链表实现

数据结构和算法是程序的灵魂,基本的数据结构分为:线性结构、树、图。线性结构又分为顺序实现的线性结构和链式实现的线性结构。链式线性结构是非随机存取结构,其get()、set()的时间复杂度是O(N);若已知要插入或删除的节点位置的话,其insert()、remove()的时间复杂度为O(1)。否则需要进行遍历操作,这时insert()、remove()的时间复杂度为O(N)。 首次写博客,望各位大牛拍砖来助学习。 以下 是单链表的实现代码: 线性表的抽象数据类型: package dataStructtion.linear; /** * 线性表的抽象数据类型 * @author xiucai …

2015-01-17 17:20 · 数据结构 · 评论(0)

线性表的顺序实现

数据结构和算法是程序的灵魂,基本的数据结构分为:线性结构、树、图。线性结构又分为顺序实现的线性结构和链式实现的线性结构。顺序实现的线性结构是一种随机存取结构,适合遍历,寻找元素;而不适合插入和删除操作。其get()、set()的时间复杂度为O(1),而插入和删除的时间复杂度为O(N)。使用java语言实现顺序存储的线性结构代码如下: 线性表的抽象数据类型 package dataStructtion.linear; /** * 线性表的抽象数据类型 * @author xiucai * @param <T> */ public interface LList<T> { /** * 判断是否为…

2015-01-17 13:22 · 数据结构 · 评论(0)