2010笔面试专栏二：数组

承蒙各位圆友支持，感受到写博客的乐趣，能跟大家分享交流我的一些经历。下面继续小结一下最近笔试面试的有关数组的题目，这些都是一些有名的IT公司考察我们有关数组的处理灵活性能力。废话不多说了，让我们直接进入题目：

1、google面试题：

（1）一个数组存放了2n+1个整数，其中有n个数出现了2次，1个数出现了1次，找出出现1次的数是多少？（可能不少人遇到过，但是当时

       我是第一次遇到，我把我的经过给大家讲一遍）

  A. 由于想在最短时间内解决，我首先想到最简单的办法，使用映射统计的办法，借助辅助数组（长度为n+1，元素为一结构体（包含数值和

      个数两个成员））进行计数，但是时间复杂度为O(n*n)，空间复杂度为O(n+1)，面试官让我改进。

  B. 接着我在纸上划划，发现如果排序后重复2次的都排在一起， 如：

              （3，3），（5，5），（18，18），（26，57），57

      那么只需要每两两考察是否一样，如果不一样（蓝色标志）则只出现1次的数（26）必定出现在左边。解法：使用快速排序对数组进行

      排序，再两两元素进行比较，相等则继续前面操作，否则输出左边的元素值。 时间复杂度为O(nlogn)。

      面试官继续询问有没更好的办法，我想时间复杂度一定是线性的O(2n+1)

C. 当时我没能想出来，后来回去后找到了解法：对数组A的所有元素做异或，即A[0]异或A[1]…… 异或A[2n]结果就是答案，理由：相同的数异或等于0，而0和任何数以后等于任何数，且异或运算可交换。

2、深信服面试：1、google面试题的变形：一个数组存放若干整数，1个数出现了奇数次，其余数出现偶数次，找出出现奇数次的数是多少?

    解法跟上一题一样使用异或运算

3、google面试：给定一个存放整数的数组，需要找出其中两个之和等于一指定的值，没有则返回提示。

     解法（如果有更好的办法，请圆友分享一下）:

   （1）先排序，再使用两个int变量low和high标记当前考察的两个元素的下标，一前一后，初始化 

          low=0,high=n-1(数组A长度)

   （2）如果low

                        如果A[low]+A[high]==key(指定的值)，则返回并退出；

                        如果A[low]+A[high]

                        否则，high—；

          如果low==high，则不存在

   （3）重复步骤（2）

代码：

int FindTwo(int A[],int n,int sum)//A已经排序（从小到大）；没找到，返回0；找到，输出并返回1{int low=0,high=n-1;while(lowsum){high--;}else{low++;}}cout<<"没找到"<
view sourceprint?   1     
4、百度笔试：给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。要求：空间复杂度O(1)
    以下是我的思路，如果大家有更好的办法可以拿出来分享。
    解法1：使用插入排序的思想，假设当前考察的元素之前的都已经符合左边为奇数，后边为偶数的条件，那么如果当前元素为偶数则不做任何操作继续考察下一元素，如果当前元素为奇数则向前寻找第一个奇数a（注意是奇数，偶数跳过），把该奇数a后面到当前元素前面的所有元素都后移一位，把当前元素插入该奇数a后一位置。重复以上步骤直到所有元素考察完毕。
代码：
void ArrangeInsert1(int A[],int n){int key=0;for(int i=1;i=0){if(key%2==1){if(A[j]%2==1){break;}}else{break;}j--;}for(int m=i-1;m>j;m--){A[m+1]=A[m];}A[j+1]=key;}}
   解法2：使用快速排序中Partition寻找枢轴位置中的高低端交换思想，只是把判断条件改为low下标元素为奇数则low++，否则low、high下标元素交换；high下标元素为偶数则high--，否则low、high下标元素交换。
代码：
view sourceprint?   01 void ArrangePartition1(int A[],int low,int high)     02 {     03     while(low     04     {     05         while(low//考察high     06         {     07             high--;     08         }     09         if(low     10         {     11             int temp=A[high];     12             A[high]=A[low];     13             A[low]=temp;     14         }     15         while(low//考察low     16         {     17             low++;     18         }     19         if(low     20         {     21             int temp=A[high];     22             A[high]=A[low];     23             A[low]=temp;     24         }     25     }     26 }  
  
  扩展：重新排列数组使得数组左边为奇数，后边为偶数，并且分别有序。
  思路：只要在前面解法判断加上另外一些条件
  解法1：对上面的解法1修改。
            使用插入排序的思想，假设当前考察的元素之前的都已经符合左边为奇数，后边为偶数并且分别有序的条件，那么如果当前元素为偶数则向前寻找第一个比它小的偶数，但是一遇到奇数就停止，如果当前元素为奇数则向前寻找第一个比它小的奇数（注意是奇数，偶数跳过），把找到位置后面到当前元素前面的所有元素都后移一位，把当前元素插入该奇数后一位置。重复以上步骤直到所有元素考察完毕。
view sourceprint?   1 代码：  view sourceprint?   1 "color: blue;">void ArrangeInsert2("color: blue;">int A[],"color: blue;">int n) { "color: blue;">int key=0; "color: blue;">for("color: blue;">int i=1;i"color: blue;">int j=i-1; "color: blue;">while(j>=0) {  
            //若key为奇数if(key%2==1){if(A[j]%2==1&&A[j]
            //若key为偶数else            
            {if(A[j]%2==1||A[j]j;m--){A[m+1]=A[m];}A[j+1]=key;}}
解法2：对上面的解法2修改。
         使用快速排序的思想，其中Partition（寻找枢轴位置函数）把
（1）若枢轴元素为偶数，对high下标元素判断条件改为如果为偶数并且大于枢轴元素，high--，否则与low下标元素交换；对low下标元素判断条件改为如果low元素为奇数或者为偶数且小于枢轴元素，low++，否则与high下标元素交换。
（2）若枢轴元素为奇数，对high下标元素判断条件改为如果为偶数或者大于枢轴元素，high--，否则与low下标元素交换；对low下标元素判断条件改为如果low元素为奇数并且小于枢轴元素，low++，否则与high下标元素交换。
代码：
int ArrangePartition2(int A[],int low,int high){int key=A[low];while(low
            if(key%2==0){if(A[high]%2==1||A[high]key){break;}}else{if(A[low]%2==0||A[low]>key){break;}}low++;}if(low