文档介绍：精品文档
精品文档
1
精品文档
精品文档
Problem1:Isitaloop?（判断链表是否有环？）
Assumethatwehaveaheadpointertoalink-：一个排好序的数组A，长度为n，现在将数组A从地点m(m<n，
m未知)分开，并将两部分交换地点，假定新数组记为B，找到时间复杂度为O(lgn)
的算法查找给定的数x是否存在数组B中？
提示：同样采用二分查找。核心思想就是确定所查找数所在的范围。经过比较3
个数（头，尾，中间）和所查找数之间的关系，能够确定下次查找的范围。
Problem14：一个排好序的数组A，长度为n，现在将数组A从地点m(m<n，
m已知)分开，并将两部分交换地点，设计一个O(n)的算法实现这样的倒置，只
允许使用一个额外空间。（循环移位的效率不高）
提示：(A’B’)’=BA
Problem15：给出Vector的一个更好实现。（STL的vector内存的倍增的，
可是每次倍增需要拷贝已存元素，平均每个元素需要拷贝一次，效率不高）
提示：可使用2^n的固定长度作为每次分派的最小单位，并有序的记录每个块
的首地点。这中构造同样能够实现线性查找，并且拷贝代价很低（仅有指针）
精品文档
精品文档
9
精品文档
精品文档
精品文档
13
精品文档
.
精品文档
精品文档
11
精品文档
精品文档
Problem16：出已排序数A，B，度分n，m，找出一个复
度（lgn）的算法，找到排在第k地点的数。
提示：二分找。
Problem17：出随意数A，B，度分n，m，找出一个复
度（lgn）的算法，找到排在第k地点的数。
提示：通最小堆k个数，不断更新，描一次完。
个提示有，求最算法！
Problem18：假数A有n个元素，元素取范是
1~n，判断数是否
存在重复元素？要求复度O(n)。
法1
：使用n的数，元素，存在
1，两次出1，即重复。
法2
：使用m的数，分大小：
n/m,2n/m
⋯..的元素个数。桶方法
法3
：累加求和。可用于求有一个元素重复的方法。
Problem19：定排好序的数A，大小n，定数X，判断A中是否存
在两数之和等于X。出一个O(n)的算法。
提示：从中向两找。利用有序的条件
精品文档
精品文档
12
精品文档
.
精品文档
精品文档
13
精品文档
精品文档
Problem20：定排好序的数A，大小n，出一个O(n)的算法，除
重复元素，且不能使用外空。
提示，既然有重复，必有冗余空。将元素放入数的前面，并下次可放位
置，不断向后描即可。
Problem21：定两个排好序的数A，B，大小分n，m。出一个高
效算法找A中的哪些元素存在B数中。
注意：一般在大数中行二分找，将小数的元素作需找的象。
更算法（刃提供）：能够使用两个指遍AB，比目前大小就能够了...
复度o(n+m)
Problem22：：有1000
桶酒，其中1桶有毒。而一旦吃了，毒性会在
1周
后作。在我用小老鼠做，要在1周内找出那桶毒酒，最少需要多少
老鼠。
答案：10只。将酒号1~1000将老鼠分号1248163264128256
512喂酒酒的号等于老鼠号的加和如：17号酒喂1号和16号老
鼠76号酒喂4号、8号和64号老鼠七天后将死掉的老鼠号加起来获得
的号就是有毒的那桶酒因2的10次方等于1024所以10只老鼠最多能够
1024桶酒
明如下：使用二制表示：01,10,100,1000,⋯,1,000,000,000。于任何
一个小于1024的数，均能够采用前面的唯一一二制数来表示。故建立。
精品文档
精品文档
14
精品文档
精品文档
精品文档
13
精品文档
.
精品文档
精品文档
16
精品文档
精品文档
Problem23：一最少个数砝，使得天平能称量1~1000的重量。
如果砝只能放，1，2，4，512最好。（只能加）
如果允砝双放，1,3,9,27最好。（可⋯）已知1,3，怎样算下
一个数。可称重量1,2,3,4。下个数x,可称重量,x-4,x-3,x-2,x-1,x,x+1,
x+2,x+3,x+4。使砝最好，所称重量不重复（浪）。故x=9。同理，
可得后边。
形算法