PAT 解题报告 (数据结构学习与实验指导) 3-05. 求链式线性表的倒数第K项

题目描述:

给定一系列正整数,请设计一个尽可能高效的算法,查找倒数第K个位置上的数字。

算法分析:

(1) 求得list长度len, 根据K和len算出顺数下来应该是第几个, 然后输出

(2) 利用两个指针, p1, p2, 首相move p2 by k positions in advance, 然后同时move p1和p2知道p2指向list的最后一个元素, 此时p1正好指向了倒数第K个元素

其实(1)和(2)的时间复杂度是一样的, 但是(2)更加精妙一点, 不用明确知道list的长度.

注意点:

如果实际存成了array的形式, 根本不用通过移动指针来获得第k个位置上的数字, 直接用array下标常数时间就能完成, 题目好像也没有规定不能这么做>_<

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on July 13, 2013