阿里面试算法题(转载)

I want to match those five numbers 3, 7, 8, 9, 87 through regular express.

Here is my thought:

- match those four numbers `3 7 8 9` var `^[3|7|8|9]$`
- match number `87` var `^87$`

Then combine them together, `(^[3|7|8|9]$|^87$)`. With some test, it seems correct. Is there any way to do that more efficiently?

-------------------------------

Q: 已知三个升序整数数组a[l], b[m]和c[n]。请在三个数组中各找一个元素,是的组成的三元组距离最小。
三元组的距离定义是:假设a[i]、b[j]和c[k]是一个三元组,那么距离为:
Distance = max(|a[i] – b[j]|, |a[i] – c[k]|, |b[j] – c[k]|)
请设计一个求最小三元组距离的最优算法,并分析时间复杂度。

用三个指针分别指向a,b,c中最小的数,计算一次他们最大距离的Distance ,然后在移动三个数中较小的数组指针,
再计算一次,每次移动一个,直到其中一个数组结束为止,最慢(l+ m + n)次,复杂度为O(l+ m + n)
---------------------------------------------------------------------------------------------------------------------
Q:设计一个最优算法来查找一n个元素数组中的最大值和最小值。
已知一种需要比较2n次的方法,请给一个更优的算法。情特别注意优化时间复杂度的常数。

把数组两两一对分组,如果数组元素个数为奇数,就最后单独分一个,然后分别对每一组的两个数比较,
把小的放在左边,大的放在右边,这样遍历下来,总共比较的次数是 N/2 次;在前面分组的基础上,那么可以得到结论,
最小值一定在每一组的左边部分找,最大值一定在数组的右边部分找,最大值和最小值的查找分别需要比较N/2 次和N/2 次;
这样就可以找到最大值和最小值了,比较的次数为
      N/2 * 3 = (3N)/2 次
---------------------------------------------------------------------------------------------------------------------
Q:有N条鱼每条鱼的位置及大小均不同,他们沿着X轴游动,有的向左,有的向右。游动的速度是一样的,两条鱼相遇大鱼会吃掉小鱼。
从左到右给出每条鱼的大小和游动的方向(0表示向左,1表示向右)。问足够长的时间之后,能剩下多少条鱼?
  
用一个栈
从左向右处理数据
1)遇到向右的鱼,压栈;
2)遇到向左的鱼,若栈空,结果+1;否则,将该鱼和栈顶比较,若栈顶鱼较大,则该鱼被吃掉,栈不变,处理下一个数据;
  若栈顶鱼小,则弹出栈顶,继续与下一个比较,直到遇到较大的鱼,该鱼被吃掉;或者栈里鱼都比该鱼小,栈清空,结果+1
3)加上最终栈中鱼的数目
--------------------------------------------------------------------------------------------------------------------
Q:  Taxicab numbers. A taxicab number is an integer that can be expressed as the sum of two cubes of 
integers in two different ways: a^3+b^3=c^3+d^3. For example, 1729=9^3+10^3=1^3+12^3.
Design an algorithm to find all taxicab numbers with a, b, c, and d less than N.
    Version 1: Use time proportional to N2logN and space proportional to N2.
    Version 2: Use time proportional to N2logN and space proportional to N.

Hints:
    Version 1: Form the sums a^3+b^3 and sort.
    Version 2: Use a min-oriented priority queue with N items.
--------------------------------------------------------------------------------------------------------------------
Q: 那地铁图 公交图查找,在实际的工程里用什么?
  
  R树划分区域, 线段树确定方案
  
Q: 德导航那个林志玲的声音,他不是让林志玲一条条的录的,合成过程中用了二分图的一个演化算法

--------------------------------------------------------------------------------------------------------------------
Q:有一个链表,每一个节点除了next指针指向一下节点以外,
又多出了一个指针random,指向链表中的任何一个节点,包括null。请给出方法完成链表的深拷贝。

这个问题的关键就在于random指针如何完成拷贝,next指针一次遍历就完成了,random指针拷贝的关键在于,
如何找到random指向的节点对应的新的节点。一般来讲,大家会想到用map来保存旧的节点到新的节点的映射,
这样得到的方法的时间复杂度为O(n),空间复杂度为O(n)。
下面是一个可行的方法:oldlist为原始链表,copylist为新的链表,oldnode为oldlist中的节点,copynode为copylist中的节点:
	1. 根据oldlist,创建copylist,只拷贝next指针
	2. 保存oldnode到oldnode.next的映射
	3. 将oldlist中的oldnode的next指针指向copylist中对应的copynode
	4. 将copylist中的copynode的random指针指向oldlist中对应的oldnode
	5. 对于copylist中的每一个节点:copynode.random=copynode.random.random.next
	6. 根据第2步,建立的映射,恢复oldlist

上面这个方法,需要额外的映射。下面介绍一个巧妙的方法,可以省去映射的部分
	1. 对oldlist中的节点,依次作如下的操作:对于第i个节点oldnode[i],生成拷贝节点copynode[i],
	并且插入在oldnode[i]和oldnode[i+1]之间,最后一个节点直接附加到oldlist后面即可。
	2. 处理每一个copynode的random拷贝,及对每一个copynode=oldnode.next, oldnode.next.random=oldnode.random.next 
	后面的next确保是copynode。
	3. 通过如下的操作,恢复oldlist,以及生成copylist 1) oldnode.next = oldnode.next.next 2)
	copynode.next = copynode.next.next 这里要注意,oldnode的最后一个节点,next是null
---------------------------------------------------------------------------------------------------------------
Q:一个数组A,数字出现的情况,只有以下三种:
	1. 一些数字只出现一次
	2. 一些数字出现两次
	3. 只有一个数字出现三次

请给出方法,找到出现三次的数字。
分析这个题目和“找数字”的题目比较相似,但是解法上类似么?之前的解法是检查某一位上的1的和,是否能够被3整除,
因为整数是32位的,可以开辟一个 32位大小的数组,这也是常数空间的。那么这个题目可以用这个方法来解决么?
因为有不确定个数的数字出现了一次,这样可以产生的余数的种类也就比较多了。 那该怎么处理呢?
hashmap的方法被称为万金油,在牺牲了空间的条件下,很好的达到了O(n)的时间复杂度。
如果要求常数空间的解法呢?之前的文章也有讨论,快排的时间复杂度是O(nlogn),然后遍历一遍,找到连续三个相同的数字。
后面这一遍遍历,可以省去,因为出现三次的数字只有一个。但总的时间复杂度仍是O(nlogn)。

是否还有其他的方法呢?有的同学给出了如下的方法:可以取得A中所有数字的乘积p,我们假设p没有溢出。
这是遍历数组中的每一个元素A[i],查看 是否p % (A[i] * A[i] * A[i]) == 0,但此时,A[i]并不是最终要找到的数字,
还需要遍历数组A,查看A[i]是否出现了三次。但这个方法整体的时间复杂度为O(n^2)。
-------------------------------------------------------------------------------------------------------------------
Q: 有数组A={5,3,8,9,16},第一次遍历有:A = {3-5,8-3,9-8,16-9}={-2,5,1,7},数组中元素和为-2+5+1+7=11;\
第二次遍历有:A = {5-(-2),1-5,7-1}={7,-4,6},元素和为9.给定数组A,求第n次遍历之后,数组中元素的和。

处理这样的题目,如果没有直接知道相关的原理,可以自己走一下一些具体的例子,这样就可以发现一些规律,根据这些规律,
再去联想解决的完整方法。经过观察,我们可以发现:
	* 对于第k次遍历而言,x_k_1、x_k_2、...、x_k_m,sum = x_k_m - x_k_1
也就是说,第k次遍历结果的和,只与第一个和最后一个元素先关。下面,就来讨论,如何求得第一个和最后一个元素。
我们看题目中的例子,先考虑第一个元素的变化
	* 第一次遍历 k = 1时:-2=3-5
	* 第二次遍历 k = 2时:7=5-(-2)=(8-3)-(3-5)=8-2*3+5
	* 第三次遍历 k = 3时:-11=-4-7=(1-5)-(5-(-2)) = ((9-8)-(8-3)) - ((8-3)-(3-5))=9-3*8+3*3-5
分析到此,想必大家已经能够明白这其中的规律,其实就是杨辉三角,老外叫帕斯卡三角。最后一个节点是类似的。
而且,真个方法的时间复杂度与遍历的次数n有关,与数组的大小无关。
-------------------------------------------------------------------------------------------------------------------
Q:搜索引擎的查询提示(suggestion)是非常重要的一个功能。现在给定查询列表,以及每一个查询对应的频率。
请设计一种查询提示的实现方案,要兼顾效果和速度。如果有其他更好的优化点,请给出详细说明。

这个功能,在搜索引擎里是非常常用的。用户在逐个输入每一个查询词的时候,给出查询的提示,用户可以选择,完成查询的输入。
这个过程,查询的提示必须要快。要不然,用户都输入完了,还没有提示,体验太差。那这个问题要怎么做呢?
给定的查询日志是这样的:
query1 num1
query2 num2
query3 num3
…
queryn numn

具体的query可能是“薛蛮子”“郭敬明”等等。用户输入时,会有哪些状态呢?
	* 薛
	* 薛蛮
	* 薛蛮子
当用户输入完“薛”的时候,就要提示以“薛”开头的哪些查询,而且是查询频率最高的10个,一般是10个。
这里是考虑总的查询的频率最高的10个,在实际的过程中,可以考虑当前热门的查询,可能总的次数比较少,
但是近几天用户差得非常多,这样的查询也一定要能够提示。
形式与目的我们都清楚了。具体做法也是比较多的,最直接的,容易想到trie树,因为上面列出的几种状态,就是前缀。
那一棵前缀树,显然是最合适的。我们在这里,就不详细说明trie的结构,只给出如何应用trie树。trie树的构建:
	* 对于所有查询,构建trie树,并且,对于查询结束的节点,进行标记,保存查询的频率。
	* 由叶子节点开始向上,比如,叶子节点A,父节点为B,B存储top10的查询,包括:所有叶子节点代表的查询,以及,
	如果B是查询结束节点,也包括B节点,按照频率排序的10个查询。
	依次向上处理,父节点的top10,是所有子节点的top10合并而成。
这样查询的时候,直接是对trie进行查询,到某一个节点,读取这个节点存储的top10查询即可,同时,这棵树,对于更新非常友好,
可以新增频率,从叶子节点,回溯到根节点,即可。
或者,采用trie树,不再节点存储top10查询,查询读取到可能类表之后再进行查询,这样会慢一些,但是内存开销稍微小一些。
但,总的来说,trie树的内存开销是非常大的。那么,我们看下面的方法。
一般,参与过搜索引擎的开发过程的,尤其是检索部分的同学,这个题目,第一个想法,可能不是trie树,而是倒排结构。
总的来讲,应用倒排结构,有如下特点,也是和trie树进行对比:
	* 查询快
	* 方便压缩,节省内存
	* 更新不方便,可以采用定期重建
具体倒排的做法:
	* 对于每一个查询的所有前缀,做为倒排的索引项,创建倒排
	* 每一个倒排,只存储top10频率的查询
除了上面介绍的之外,还需要考虑拼音等,思路大体相同。只不过更加需要注意内存的消耗。
---------------------------------------------------------------------------------------------------------
Q: 从1到n,n个数字,每个数字只出现一次。现在,随机拿走一个数字,请给出方法,找到这个数字。
如果随机拿走两个数字呢?如果随机拿走k个数字呢?

这个题目的含义是:n-1互不相同的整数,取值范围是[1,n],请找到1-n中,没有出现的整数(好像更难理解了:))。
当缺少一个数字的时候,很简单,计算1到n的和sum_more,然后再将n-1个整数求和,得到sum_less,
则消失的数字就是(sum_more - sum_less)。
如果消失两个数字呢?按照上面的方法,假设消失的两个数字分别为a和b,1 <= a, b <= n,
我们可以得到a + b = sum_more - sum_less。只有一个等式,无法确定a和b的值是多少。根据我们以前学习解方程式的经验,
我们还需要一个等式,才能确定a和b的值。现在已知的条件,就只有sum_more,sum_less,这两个分别是n个数的和,以及n-2个数的和,
则最终还是要在这些数字的运算形式上做文章。考虑如下两个形式:
	* square_sum_more = n个数的平方和
	* square_sum_less = n-2个数的平方和
有,square_sum_more - square_sum_less = a ^ 2 + b ^ 2。又构造了一个式子。这样解如下两个式子,得到a和b,即可:
	* square_sum_more - square_sum_less = a ^ 2 + b ^ 2
	* sum_more - sum_less = a + b
解比较简单了,由第二个式子得:b = sum_more - sum_less - a,带入第一个式子,则第一个式子,只有a。
如果消失三个数字呢?根据上面处理两个数字的情况,有如下的式子:
	* sum_more - sum_less = a + b + c
	* square_sum_more - square_sum_less = a ^ 2 + b ^ 2 + c ^ 2
	* cube_sum_more - cube_sum_less = a ^ 3 + b ^ 3 + c ^ 3
解出a,b,c即可。
依次类推,当消失k个数字的时候,算法的时间复杂度为O(kn)。
另外,微博上的一位同学@曹鹏博士,给出了一个O(nlogn)的解法,也是非常巧妙的,具体是采用分治法:
知道1-n最低bit有多少个为0,多少个为1。然后统计一下,给出的数最低bit有多少个为0,多少个为1;
然后就知道从最低bit为0的那部分取走了k0个数,从最低bit为1那部分取走了k1个数。 其中,k0 + k1 = k。 
然后把那些数按照最低bit为0,为1分开。问题变为两个子问题k0,k1,然后再考虑次低bit。很不错的解法。
-----------------------------------------------------------------------------------------------------------------
Q:给定一个数X,他的兄弟数Y定义为:是由X中的数字组合而成,并且Y是大于X的数中最小的。
例如,38276的兄弟数字为38627。给定X,求Y。

这个题目当然有暴力的方法,列出所有的排列组合,然后然后找到大于X中,最小的Y。即,找到兄弟数字。那有没有更好的方法呢?
不想对所有情况进行穷举,就要想办法,尽可能缩小要处理的范围,一般的思路,从右边开始,两两交换,查看是否可以找到Y,
最开始考虑两位,进而考虑三位,依次类推,那么如何确定,要考虑多少位呢?
假设X的形式如下:x1x2x3...xky1y2y3y4,并且其中y1>y2>y3>y4,xk<y1。则,交换不可能在y1y2y3y4内部发生,
以为这几个数字,任意两个交换,X值就变小了,而Y是大于X的。所以y1到y4是不行的。
那么xk行么?完全可以,至少和y1交换,数字变大了。 那么到底要和哪个数字交换,进而保证变化最小呢?
很显然,要找到y1到y4中,大于xk的值里,最小的一个。这个值交换之后,既保证了不会增加太多,也不会减少。
假设就是y3,此时Y是x1x2x3...y3y1y2xky4,这个数是从y3那位开始,大于X的,无论后面的几位是什么。
显然易见,最小的Y就是y1y2xky4要从小到大排序的。

下面以一个具体例子来说明上述过程:
34722641
首先找到,从右边开始的递增的、尽可能长的数位,这里是641。
34722(641)
则,选取前一位数字2,进行交换。641中,大于2的最小的值是4,则作如下交换:
34724(621)
为了得到最小值,对621,从小到大进行排序,得到
34724126
则,Y为34724126.
-------------------------------------------------------------------------------------------------------------
Q:有n对喜鹊。每一对可以表示为(x,y),x、y是喜鹊的编号,并且任意一对,x总是小于y。(c,d)可以连接在(a,b)之后,当且仅当b<c。
多对喜鹊连接在一起,就构建成了鹊桥。给定n对喜鹊,请你构建最长的鹊桥,来帮助有情人相会。

首先,要理解这个题目的意思。具体例子说明,给定下面的例子:
(15,40)(5,8)(1,10)(30,31)(34,35)(9,20)(36,37)(2,4)其中,(2,4)和(5,8)能够连接起来,(5,8)和(9,20)能够连接起来,
则它们可以都连接起来,为(2,4)(5,8)(9,20)。这一段鹊桥,长度为3。依次类推,还有其他的情况。
然后,理解了题意,该如何解决呢?假设(a,b)(c,d)(e,f)是可以连接起来的三对喜鹊。
则它们的关系如下: b<c,d<e,有根据a<b,c<d,e<f。得到,a<b<c<d<e<f,即b<d<f(从a<c<e出发考虑,也是一样的)。
我们可以想象,以每一对喜鹊的第二只编号为基准,进行排序,最终的结果,可以通过如下列表产生。
(2,4)(5,8)(1,10)(9,20)(30,31)(34,35)(36,37)(15,40)怎么找到最长的鹊桥呢?其实就是在上表中,找到最长递增子序列,
只不过,在比较连个喜鹊对(a,b)(c,d)的时候,是b和c进行比较即可。这个时间复杂度是O(n^2)的。
-----------------------------------------------------------------------------------------------------------------
Q:n根长度不一的棍子,判断是否有三根棍子可以构成三角形,并且找到周长最长的三角形。

首先能够构成三角形的三根棍子需要满足什么条件呢?这个简直就是常识了:
最长棍子的长度 < 另外两根棍子的长度和
这是重要条件。
那么接下来该怎么办呢?暴力法——不要总觉得这是耻辱,要这样想:这是一个好开端。三条边,三层循环。时间复杂度为O(n^3)。
这在一般的题目中,都是无法接受的。如何改进的呢?棍子有长有短,我们要找到的是周长最长的。
我们可以对棍子的长度,从大到小排序。从最长的开始找符合构成三角形条件的。找到的第一个就是周长最长的。
下面我们来说明,为什么第一个找到的,就是最长的。假设我们有如下长度的棍子,并且长度一次递减。
abcdefg假设opq是第一个可以构成三角形的棍子,假设还存在xyz,构成三角形,且,x+y+z > o + p + q, 
因为opq是第一个三角形,则x<=o。则y+z > p+q,任取y、z,则可以找到,o,y,z为一个三角形,周长大于opq,
并且,这个三角形,在opq之前找到(因为y或者z,大于p或者q,先遍历到)。这个与adf是第一个的假设是矛盾的。
所以,不存在xyz构成三角形,周长大于adf。
那么如果找到第一个能够构成三角形的三根棍子呢?现在棍子的长度已经是排序的。
abcdefg很明显,我们只需要依次考虑,相邻三个元素是否能够构成三角形即可。因为,如果acd构成三角形,abc一定是,
而且,周长还要更长。所以这里O(n),就可以找到周长最长的三角形。前面排序是O(nlogn)。则,总的时间复杂度是O(nlogn).
--------------------------------------------------------------------------------------------------------------------
Q: 一个整数,可以表示为二进制的形式,请给出尽可能多的方法对二进制进行逆序操作。
例如:10000110 11011000的逆序为 00011011 01100001

A:
直接的方法,很容易想到:有如下代码: int v = 111;
int r = v;
int s = 32; 
for (; 0 != v; v >>= 1) { 
    r <<= 1;
    r |= v & 1;
    s--;
}
r <<= s;
System.out.println(r);
代码比较好理解,取到v的最低位,作为r的最高位;v每取一次最低位,则右移一位;r每确定一位,则左移一位。
同时记录移动了多少位,最终要补齐。

通过查表的方法在遇到位操作的问题时,往往题目中限定了总的位数,比如这个题目,我们可以认为32位。
这就给我们带来了一个以空间换时间的解决思路:查表法。
位数是固定的,可以申请空间,存储预先计算好的结果,在计算其他的结果的时候,则查表即可。
32位相对于查表来讲,还是太大了。既然这样缩小范围,32个bit,也就是4个byte。每个byte 8bit,可以表示0-255的整数。
可以通过申请256大小的数组,保存这256个整数,二进制逆序之后的整数。然后将一个32位的整数,划分为4个byte,
每一个byte查表得到逆序的整数:r1,r2,r3,r4。按照r4r3r2r1顺序拼接二进制得到的结果就是最终的答案。

我们这里主要分析这个巧妙的方法,核心思想是:分治法。即:
	* 逆序32位分解为两个逆序16位的
	* 逆序16位分解为两个逆序8位的
	* 逆序8位分解为两个逆序4位的
	* 逆序4位分解为两个逆序2位的

最后一个2位的逆序,直接交换即可。也就是分治递归的终止条件。但是,在上面的过程中,还没有应用到位操作的技巧
。根据动态规划的思想,我们可以自底向上的解决这个问题:
	* 每2位为一组,进行交换,完成2位逆序
	* 每4位为一组,前面2位与后面2位交换,完成4位逆序
	* 每8位为一组,前面4位和后面4为交换,完成8位的逆序
	* 每16位为一组,前面8位和后面8位交换,完成16位的逆序
	* 2组16位的交换,完成32位的逆序

示例代码如下:
int v = 111;
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
v = ( v >> 16 ) | ( v << 16);
------------------------------------------------------------------------------------------------------------------
Q:输入数组[a1,a2,...,an,b1,b2,...,bn],构造函数,使得输出为,[a1,b1,a2,b2,...,an,bn],注意:方法要是in-place的。

A:通过观察输入输出的格式,直接通过将b1进行交换,直至目标的位置,其他元素也如此操作。直到完成变换。如下的过程:
a1 a2 a3 a4 b1 b2 b3 b4
确定b1的位置,b1要和前面3个元素依次交换。
a1b1a2a3a4b2b3b4
确定b2的位置,b2要和前面的2个元素一次交换,同样为了保证in-place。注意交换次数少了一次。
a1b1a2b2a3a4b3b4
依次确定b3和b4的位置,b4是最后的元素,不需进行交换,b3需要交换一次。
a1b1a2b2a3b3a4b4
通过上面的分析,则整体的交换次数,3+2+1=6,不失一般性(n-1)+…+1,时间复杂度O(n^2)。

特别的方法同样针对上面的例子:
第一步:交换最中间的一对元素,得到
a1a2a3b1a4b2b3b4
第二步:交换最中间的两对元素,得到
a1a2b1a3b2a4b3b4
第三步:交换最中间的三对元素,得到
a1b1a2b2a3b3a4b4
完毕,得到结果。
在上面的交换中,交换的次数分别为1,2,3,推而广之,1,…,n-1,则时间复杂度仍旧是O(n^2)的。

in-place的O(n)方法这个问题,是存在O(n)时间复杂度的in-place算法的。但是,并不是很好理解。
首先,对2n=3^k - 1的情况下,k是整数。这时候可以通过几个cyclic shift解决。
每个cycle的起始位置是3^i, i=0,1,...,k-1. cycle里面元素下标的符合这样的模式(3^i×2^j) mod (2n+1)
举例说明:k=2时,2n=8.
假设一个数列是[1,2,3,4,5,6,7,8]
那么这几个cycle是
i=0, 3^i=1, [1,2,4,8,16,32] mod 9 = [1,2,4,8,7,5]
i=1, 3^i=3, [3,6] mod 9 = [3,6] 
显然这些cycle都是闭合的,比如对[1,2,4,8,7,5], 5×2 mod 9 = 1, 对[3,6] 6×2 mod 9 = 3

下面做这两个cyclic shift
做完第一个后:
[1,2,3,4,5,6,7,8] -> [5,1,3,2,7,6,8,4]
做完第二个后:
[5,1,3,2,7,6,8,4] -> [5,1,6,2,7,3,8,4]
搞定。

其次对2n!=3^k - 1的情况下,找一个最大的m,m满足2m=3^k - 1并且m 比如假设n=6,那么m=4.
假设一个素列A=[1,2,3,4,5,6,7,8,9,10,11,12]
首先A[m+1,...,n+m]做一个距离为m的右循环。
也就是[5,6,7,8,9,10]做一个距离为m的右循环,变成[7,8,9,10,5,6]
做完这个循环,[1,2,3,4,5,6,7,8,9,10,11,12]->[1,2,3,4,7,8,9,10,5, 6, 11,12]
然后对前2m项,做1的操作,[1,2,3,4,7,8,9,10,5, 6, 11,12]->[7,1,8,2,9,3,10,4,5, 6, 11,12] 
然后对于下的2*(n-m)项[5,6,11,12]递归操作。

def getIndex(curIdx, N):
	return (curIdx%2)*N + (curIdx/2)
	
def convertArray(arr):
	N = len(arr)/2
	for curIdx in range(len(arr)):
		swapIdx = getIndex(curIdx, N)
		while swapIdx < curIdx:
			swapIdx = getIndex(swapIdx, N)
		arr[curIdx], arr[swapIdx] = arr[swapIdx], arr[curIdx]
		

def convertArray_extraspace(arr):
	N = len(arr)/2
	return [arr[getIndex(i, N)] for i in range(len(arr))]
	
def main():

if __main__ == 'main'
	main()
-------------------------------------------------------------------------------------------------------------
Q: n只蚂蚁以每秒1cm的速度在长为Lcm的竿子上爬行。蚂蚁爬到终点会掉下来。两只蚂蚁相遇时,只能调头爬回去。
对于每一只蚂蚁i,给定其距离竿子左端的距离x[i],但是我们不知道蚂蚁的初始朝向。计算,所有蚂蚁掉落需要的最短时间和最长时间。

我们在摘要中说道,这个题目其实是考察大家想象力的。想象力在哪里呢?我们首先来看看最短时间的情况,
直觉上来讲,所有的蚂蚁都超最近的一端走,是需要最短时间的。那么这时,会不会发生碰撞呢?
显然是不能的,A和B是两只不同的蚂蚁。
…BA
…
假设A到左端近,距离为LA<L/2。B到右端近,距离为LB<L/2。LA+LB<L。但从上表看,LA+LB显然要大于L。
下面考虑最长时间的情况,也是该发挥想象力的地方。当两只蚂蚁相遇的时候,本来是要调头爬回去的。
这与直接交错走过去有什么不同呢?蚂蚁的速度是一样的。大家可以举几个具体的例子,看看这两种情况,差别在哪里。例如:
B A
	* 当相遇调头时,A和B都调下来的最长时间是4秒。A向左一格,然后调头向右三格
	* 当相遇交错走过时,A向左走三格掉落,B向右走四格掉落。则最长时间为4秒。

这并不是巧合。可以认为是同样的情况。主要的原因就是蚂蚁的速度是相同的,可以认为是独立的。
这样,求所有蚂蚁都掉落的最长时间,就是找离某一端距离最长的蚂蚁,然后向着这一端走,所需要的时间。算法的时间复杂度为O(n)。
后面求最长时间的关键就是,发挥想象,找到调头和交错走过实际上是一样的。就搞定了。