由一个面试题目想到的_求职面试_非技术区_程序员俱乐部

今天看到一个特别简单的题目，就是说有两个数组A和B，假设都是整数类型的，而且都是从小到大排好序的，A里面，从下标0开始，有X个数；B里面有Y个数，A的长度是X+Y，B的长度是Y，就是说A里面能放下所有A和B的数。目标是设计一个算法，把所有这些数字都放到A里面去，当然结果要是排序的。

这个题目再简单不过了，就是倒着做merge sort。具体说就是用两个下标，分别从A和B的数据尾巴开始，做合并。合并的结果从A的最后一个位置开始放，最后A里面就是A和B的合并的并且排序的结果了。

说到这个题目，想起另外一个比较难的题目来。不过还是用一个简单的题目开始吧：假如有一个很长的整数数组，要求用这个数组实现两个堆栈。

这个题目很简单，就是用两个栈指针，然后分别从数组的两头开始，向中间生长。具体写程序的时候，检查一下两个指针是否相遇就可以了。

然后题目就难了一点：如何用一个数组实现三个堆栈？

答案其实是上面那个题目的一个挺巧妙的扩展：三个堆栈里面的两个，还是按照上面的办法做；然后第三个堆栈，从数组三分之一的地方开始，向三分之二的方向生长。具体说来：

假设数组是A，长度是L，那么三个堆栈分别从下标0，L，和1/3L的地方开始生长。假设三个堆栈的栈顶指针分别是x，y和z，那么当栈生长到一定时间的时候，空间会不够用，可能会有以下情况：

1. x生长到了1/3L
2. y和z相遇

这两种情况下，数组都会有一段空间空闲（如果三个栈一样长，那就结束了），或者是A[x，1/3L]，或者是A[y，z]。那么把这个空间继续按照上面的办法分割，直到空间用完为止。

本文来自：http://www.meirendaddy.com/blog/?p=95