Questions.txt

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)。
后面求最长时间的关键就是，发挥想象，找到调头和交错走过实际上是一样的。就搞定了。