算法面试（数组）

数组相关：
http://www.cnblogs.com/graphics/archive/2010/08/24/1761620.html

1.求数组中相邻元素的最短距离，最长距离？
最短：1）排序 扫描 2）分治法   复杂度都为O(nlogn)
最长：1）分治法
     2）最大距离一定不小于 d = (max - min)/ (N - 1);
        按照d间隔将元素化为N个桶，保持每个桶中的最大和最小元素
        最大的差值处于两个不同的桶中，即某个桶的最小值和前一个非空桶的最大值的差值
        时空复杂度均为O（n）
扩展：二维的点
  最短：最近点对算法（分治）
  最长：点集的直径，先寻找凸包，然后求映对，比较

2.求两个有序数组的共同元素
 1）两个下标移动
 2）折半查找

这到题还有其他的解法，比如对于a中任意一个元素，在b中对其进行Binary Search，因为a中有n个元素，而在b中进行Binary Search需要logn。所以找出全部相同元素的时间复杂度是O(nlogn)。

另外，上面的方法，只要b有序即可，a是否有序无所谓，因为我们只是在b中做Binary Search。如果a也有序的话，那么再用上面的方法就有点慢了，因为如果a中某个元素在b中的位置是k的话，那么a中下一个元素在b中的位置一定位于k 的右侧，所以本次的搜索空间可以根据上次的搜索结果缩小，而不是仍然在整个b中搜索。也即如果a和b都有序的话，代码可以做如下修改，记录上次搜索时b中 元素的位置，作为下一次搜索的起始点。

总结：需要知道两个数组都是否有序，还有元素个数，如果一个元素很多，另外一个很少，那么将少的排序，可以认为是常数，然后折半查找，可以视为常数，故复杂度O(n)

3.求1-n个数中多的一个数或少的一个数

  1）求和 2）异或（与1-n一起异或）

 扩展: 1）求出现奇数次的元素(抽牌，问抽了什么)

      2）缺两个不同的数，异或后，根据某位为1和0，将元素分组

        然后再异或

      3）缺两个数（可能相同）

         列方程解答

         x + y = a

         xy = b(或 x^2 + y^2 = b)

4.求数组中满足给定和的数对

  1)一个数组  2）两个数组
   排序，两个指针扫描
扩展：集合S， 一个数N，求集合中最接近N的子集

5. 数组N，求任意N-1个数乘积的最大值
  可以先计正数、负数、0和绝对值最小的正数和负数，然后判断结果是什么。
6. 子数组最大和，最大积

7.给定含有n个元素的整型数组a，其中包括0元素和非0元素，对数组进行排序，要求：

1. 排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相对位置不变

2. 不能使用额外存储空间

例子如下

输入 0, 3, 0, 2, 1, 0, 0

输出 0, 0, 0, 0, 3, 2, 1

void Arrange(int* a, int n)
{
    int k = n - 1 ;
    while(a[k]) --k;
    if(k <= 0) return;
    for (int i = k - 1; i >= 0; --i)
    {
        if (a[i] != 0) swap(a[i], a[k--]);
    }
}

8.n选m个，输出组合