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<high，考察：
如果A[low]+A[high]==key(指定的值)，則返回并退出；
如果A[low]+A[high]<key，則low++；
否則，high—；
如果low==high，則不存在
（3）重復步驟（2）
代碼：
{
int low=0,high=n-1;
while(low<high)
{
if(A[low]+A[high]==sum)
{
cout<<"找到，兩個數的下標為"<<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、百度筆試：給定一個存放整數的數組，重新排列數組使得數組左邊為奇數，右邊為偶數。要求：空間復雜度O(1)
以下是我的思路，如果大家有更好的辦法可以拿出來分享。
解法1：使用插入排序的思想，假設當前考察的元素之前的都已經符合左邊為奇數，后邊為偶數的條件，那么如果當前元素為偶數則不做任何操作繼續考察下一元素，如果當前元素為奇數則向前尋找第一個奇數a（注意是奇數，偶數跳過），把該奇數a后面到當前元素前面的所有元素都后移一位，把當前元素插入該奇數a后一位置。重復以上步驟直到所有元素考察完畢。
代碼：
{
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下標元素為奇數則low++，否則low、high下標元素交換；high下標元素為偶數則high--，否則low、high下標元素交換。
代碼：
{
while(low<high)
{
while(low<high&&A[high]%2==0)//考察high
{
high--;
}
if(low<high)
{
int temp=A[high];
A[high]=A[low];
A[low]=temp;
}
while(low<high&&A[low]%2==1)//考察low
{
low++;
}
if(low<high)
{
int temp=A[high];
A[high]=A[low];
A[low]=temp;
}
}
}
擴展：重新排列數組使得數組左邊為奇數，后邊為偶數，并且分別有序。
思路：只要在前面解法判斷加上另外一些條件
解法1：對上面的解法1修改。
使用插入排序的思想，假設當前考察的元素之前的都已經符合左邊為奇數，后邊為偶數并且分別有序的條件，那么如果當前元素為偶數則向前尋找第一個比它小的偶數，但是一遇到奇數就停止，如果當前元素為奇數則向前尋找第一個比它小的奇數（注意是奇數，偶數跳過），把找到位置后面到當前元素前面的所有元素都后移一位，把當前元素插入該奇數后一位置。重復以上步驟直到所有元素考察完畢。
代碼：
{
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&&A[j]<key)
{
break;
}
}
else
{
if(A[j]%2==1||A[j]<key)
{
break;
}
}
j--;
}
for(int m=i-1;m>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 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);
}
}
留言列表
