承蒙各位圓友支持,，感受到寫博客的樂趣,，能跟大家分享交流我的一些經(jīng)歷,。下面繼續(xù)小結一下最近筆試面試的有關數(shù)組的題目,，這些都是一些有名的IT公司考察我們有關數(shù)組的處理靈活性能力,。廢話不多說了,，讓我們直接進入題目：

1、google面試題：

（1）一個數(shù)組存放了2n+1個整數(shù),，其中有n個數(shù)出現(xiàn)了2次,，1個數(shù)出現(xiàn)了1次，找出出現(xiàn)1次的數(shù)是多少,？（可能不少人遇到過,，但是當時

       我是第一次遇到，我把我的經(jīng)過給大家講一遍）

  A. 由于想在最短時間內(nèi)解決，我首先想到最簡單的辦法,，使用映射統(tǒng)計的辦法,，借助輔助數(shù)組（長度為n+1，元素為一結構體（包含數(shù)值和

      個數(shù)兩個成員））進行計數(shù),，但是時間復雜度為O(n*n),，空間復雜度為O(n+1)，面試官讓我改進,。

  B. 接著我在紙上劃劃,，發(fā)現(xiàn)如果排序后重復2次的都排在一起， 如：

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

      那么只需要每兩兩考察是否一樣，如果不一樣（藍色標志）則只出現(xiàn)1次的數(shù)（26）必定出現(xiàn)在左邊,。解法：使用快速排序對數(shù)組進行

      排序,，再兩兩元素進行比較，相等則繼續(xù)前面操作,，否則輸出左邊的元素值,。 時間復雜度為O(nlogn)。

      面試官繼續(xù)詢問有沒更好的辦法,，我想時間復雜度一定是線性的O(2n+1)

C. 當時我沒能想出來,，后來回去后找到了解法：對數(shù)組A的所有元素做異或，即A[0]異或A[1]…… 異或A[2n]結果就是答案,，理由：相同的數(shù)異或等于0,，而0和任何數(shù)以后等于任何數(shù)，且異或運算可交換,。

2,、深信服面試：1、google面試題的變形：一個數(shù)組存放若干整數(shù),，1個數(shù)出現(xiàn)了奇數(shù)次,，其余數(shù)出現(xiàn)偶數(shù)次，找出出現(xiàn)奇數(shù)次的數(shù)是多少?

    解法跟上一題一樣使用異或運算

3,、google面試：給定一個存放整數(shù)的數(shù)組,，需要找出其中兩個之和等于一指定的值,，沒有則返回提示,。

     解法（如果有更好的辦法,，請圓友分享一下）:

   （1）先排序，再使用兩個int變量low和high標記當前考察的兩個元素的下標,，一前一后,，初始化 

          low=0,high=n-1(數(shù)組A長度)

   （2）如果low<high，考察：

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

                        如果A[low]+A[high]<key，則low++,；

                        否則,，high—；

          如果low==high,，則不存在

   （3）重復步驟（2）

代碼：

int FindTwo(int A[],int n,int sum)//A已經(jīng)排序（從小到大）,；沒找到，返回0,；找到,，輸出并返回1
{
int low=0,high=n-1;
while(low<high)
{
if(A[low]+A[high]==sum)
{
cout<<"找到，兩個數(shù)的下標為"<<low<<"和"<<high<<endl;
cout<<A[low]<<"+"<<A[high]<<"="<<sum<<endl;
return 1;
}
else if(A[low]+A[high]>sum)
{
high--;
}
else
{
low++;
}
}
cout<<"沒找到"<<endl;
return 0;
}

4,、百度筆試：給定一個存放整數(shù)的數(shù)組,，重新排列數(shù)組使得數(shù)組左邊為奇數(shù)，右邊為偶數(shù),。要求：空間復雜度O(1)

    以下是我的思路,，如果大家有更好的辦法可以拿出來分享。

    解法1：使用插入排序的思想,，假設當前考察的元素之前的都已經(jīng)符合左邊為奇數(shù),，后邊為偶數(shù)的條件，那么如果當前元素為偶數(shù)則不做任何操作繼續(xù)考察下一元素,，如果當前元素為奇數(shù)則向前尋找第一個奇數(shù)a（注意是奇數(shù),，偶數(shù)跳過），把該奇數(shù)a后面到當前元素前面的所有元素都后移一位,，把當前元素插入該奇數(shù)a后一位置,。重復以上步驟直到所有元素考察完畢。

代碼：

void ArrangeInsert1(int A[],int n)
{
int key=0;
for(int i=1;i<n;i++)
{
key=A[i];
int j=i-1;
while(j>=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下標元素為奇數(shù)則low++,，否則low、high下標元素交換,；high下標元素為偶數(shù)則high--,，否則low,、high下標元素交換。

代碼：

  擴展：重新排列數(shù)組使得數(shù)組左邊為奇數(shù),，后邊為偶數(shù),，并且分別有序。

  思路：只要在前面解法判斷加上另外一些條件

  解法1：對上面的解法1修改,。

            使用插入排序的思想,，假設當前考察的元素之前的都已經(jīng)符合左邊為奇數(shù)，后邊為偶數(shù)并且分別有序的條件,，那么如果當前元素為偶數(shù)則向前尋找第一個比它小的偶數(shù),，但是一遇到奇數(shù)就停止，如果當前元素為奇數(shù)則向前尋找第一個比它小的奇數(shù)（注意是奇數(shù),，偶數(shù)跳過）,，把找到位置后面到當前元素前面的所有元素都后移一位，把當前元素插入該奇數(shù)后一位置,。重復以上步驟直到所有元素考察完畢,。

            //若key為奇數(shù)
if(key%2==1)
{
if(A[j]%2==1&&A[j]<key)//A[j]為奇數(shù)并小于key，則跳出循環(huán)
{
break;
}
}

            //若key為偶數(shù)
else            

            {
if(A[j]%2==1||A[j]<key)//A[j]為奇數(shù)或者A[j]大于key,，則跳出循環(huán)
{
break;
}
}
j--;
}
for(int m=i-1;m>j;m--)
{
A[m+1]=A[m];
}
A[j+1]=key;
}
}

解法2：對上面的解法2修改,。

         使用快速排序的思想，其中Partition（尋找樞軸位置函數(shù)）把

（1）若樞軸元素為偶數(shù),，對high下標元素判斷條件改為如果為偶數(shù)并且大于樞軸元素,，high--，否則與low下標元素交換,；對low下標元素判斷條件改為如果low元素為奇數(shù)或者為偶數(shù)且小于樞軸元素,，low++，否則與high下標元素交換,。

（2）若樞軸元素為奇數(shù),，對high下標元素判斷條件改為如果為偶數(shù)或者大于樞軸元素，high--,，否則與low下標元素交換,；對low下標元素判斷條件改為如果low元素為奇數(shù)并且小于樞軸元素，low++,，否則與high下標元素交換,。

代碼：

int ArrangePartition2(int A[],int low,int high)
{
int key=A[low];
while(low<high)
{
while(low<high)//考察high
{

            if(key%2==0)
{
if(A[high]%2==1||A[high]<key)
{
break;
}
}
else
{
if(A[high]%2==1&&A[high]<key)
{
break;
}
}
high--;
}
if(low<high)
{
int temp=A[high];
A[high]=A[low];
A[low]=temp;
}
while(low<high)//考察low
{
if(key%2==0)
{
if(A[low]%2==0&&A[low]>key)
{
break;
}
}
else
{
if(A[low]%2==0||A[low]>key)
{
break;
}
}
low++;
}
if(low<high)
{
int temp=A[high];
A[high]=A[low];
A[low]=temp;
}
}
return low;
}
void QuickArrange(int A[],int low,int high)
{
if(low<high)
{
int pos=ArrangePartition2(A,low,high);
QuickArrange(A,low,pos-1);
QuickArrange(A,pos+1,high);
}
}