數組是最基本的數據結構，關于數組的面試題也屢見不鮮，本文羅列了一些常見的面試題，僅供參考。目前有以下18道題目。

數組求和

求數組的最大值和最小值

求數組的最大值和次大值

求數組中出現次數超過一半的元素

求數組中元素的最短距離

求兩個有序數組的共同元素

求三個數組的共同元素

找出數組中唯一的重復元素

找出出現奇數次的元素

求數組中滿足給定和的數對

最大子段和

最大子段積

數組循環移位

字符串逆序

組合問題

合并兩個數組

重排問題

找出絕對值最小的元素

數組求和

給定一個含有n個元素的整型數組a，求a中所有元素的和。可能您會覺得很簡單，是的，的確簡單，但是為什么還要說呢，原因有二，第一，這道題要求用遞歸法，只用一行代碼。第二，這是我人生中第一次面試時候遇到的題，意義特殊。

分析

簡單說一下，兩種情況

如果數組元素個數為0，那么和為0。

如果數組元素個數為n，那么先求出前n - 1個元素之和，再加上a[n - 1]即可

代碼

//數組求和
intsum(int*a,intn)
{
returnn==0?0:sum(a,n-1)+a[n-1];
}

求數組的最大值和最小值

給定一個含有n個元素的整型數組a，找出其中的最大值和最小值

分析

常規的做法是遍歷一次，分別求出最大值和最小值，但我這里要說的是分治法(Divide and couquer)，將數組分成左右兩部分，先求出左半部份的最大值和最小值，再求出右半部份的最大值和最小值，然后綜合起來求總體的最大值及最小值。

這是個遞歸過程，對于劃分后的左右兩部分，同樣重復這個過程，直到劃分區間內只剩一個元素或者兩個元素。

代碼

//求數組的最大值和最小值，返回值在maxValue和minValue
voidMaxandMin(int*a,intl,intr,int&maxValue,int&minValue)
{
if(l==r)//l與r之間只有一個元素
{
maxValue=a[l];
minValue=a[l];
return;
}

if(l+1==r)//l與r之間只有兩個元素
{
if(a[l]>=a[r])
{
maxValue=a[l];
minValue=a[r];
}
else
{
maxValue=a[r];
minValue=a[l];
}
return;
}

intm=(l+r)/2;//求中點

intlmax;//左半部份最大值
intlmin;//左半部份最小值
MaxandMin(a,l,m,lmax,lmin);//遞歸計算左半部份

intrmax;//右半部份最大值
intrmin;//右半部份最小值
MaxandMin(a,m+1,r,rmax,rmin);//遞歸計算右半部份

maxValue=max(lmax,rmax);//總的最大值
minValue=min(lmin,rmin);//總的最小值
}

求數組的最大值和次大值

給定一個含有n個元素的整型數組，求其最大值和次大值

分析

思想和上一題類似，同樣是用分治法，先求出左邊的最大值leftmax和次大值leftsecond，再求出右邊的最大值rightmax和次大值rightsecond，然后合并，如何合并呢？分情況考慮

1 如果leftmax > rightmax，那么可以肯定leftmax是最大值，但次大值不一定是rightmax，但肯定不是rightsecond，只需將leftsecond與rightmax做一次比較即可。

2 如果rightmax > leftmax，那么可以肯定rightmax是最大值，但次大值不一定是leftmax，但肯定不是leftsecond，所以只需將leftmax與rightsecond做一次比較即可。

注意

這種方法無法處理最大元素有多個的情況，比如3,5,7,7將返回7，7而不是7,5。感謝網友 從無到有靠誰人 指出。

代碼

//找出數組的最大值和次大值，a是待查找的數組，left和right是查找區間，max和second存放結果
voidMaxandMin(inta[],intleft,intright,int&max,int&second)
{
if(left==right)
{
max=a[left];
second=INT_MIN;
}
elseif(left+1==right)
{
max=a[left]>a[right]?a[left]:a[right];
second=a[left]rightmax)
{
max=leftmax;
second=leftsecond>rightmax?leftsecond:rightmax;
}
else
{
max=rightmax;
second=leftmax

	

	求數組中出現次數超過一半的元素

	給定一個n個整型元素的數組a，其中有一個元素出現次數超過n / 2，求這個元素。據說是百度的一道題

	分析

	設置一個當前值和當前值的計數器，初始化當前值為數組首元素，計數器值為1，然后從第二個元素開始遍歷整個數組，對于每個被遍歷到的值a[i]

	1 如果a[i]==currentValue，則計數器值加1

	2 如果a[i] != currentValue， 則計數器值減1，如果計數器值小于0，則更新當前值為a[i]，并將計數器值重置為1

	代碼

	
//找出數組中出現次數超過一半的元素
intFind(int*a,intn)
{
intcurValue=a[0];
intcount=1;

for(inti=1;i

	

	另一個方法是先對數組排序，然后取中間元素即可，因為如果某個元素的個數超過一半，那么數組排序后該元素必定占據數組的中間位置。

	求數組中元素的最短距離

	給定一個含有n個元素的整型數組，找出數組中的兩個元素x和y使得abs(x - y)值最小

	分析

	先對數組排序，然后遍歷一次即可

	代碼

	
intcompare(constvoid*a,constvoid*b)
{
return*(int*)a-*(int*)b;
}

//求數組中元素的最短距離
voidMinimumDistance(int*a,intn)
{
//Sort
qsort(a,n,sizeof(int),compare);

inti;//Indexofnumber1
intj;//Indexofnumber2

intminDistance=numeric_limits::max();
for(intk=0;k

	

	求兩個有序數組的共同元素

	給定兩個含有n個元素的有序（非降序）整型數組a和b，求出其共同元素，比如

	a = 0, 1, 2, 3, 4

	b = 1, 3, 5, 7, 9

	輸出 1, 3

	分析

	充分利用數組有序的性質，用兩個指針i和j分別指向a和b，比較a[i]和b[j]，根據比較結果移動指針，則有如下三種情況

	a[i] < b[j]，則i增加1，繼續比較

	a[i] == b[j]，則i和j皆加1，繼續比較

	a[i] < b[j]，則j加1，繼續比較

	重復以上過程直到i或j到達數組末尾。

	代碼

	
//找出兩個數組的共同元素
voidFindCommon(int*a,int*b,intn)
{
inti=0;
intj=0;

while(ib[j]
++j;
}
}


	

	這到題還有其他的解法，比如對于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中元素的位置，作為下一次搜索的起始點。

	求三個數組的共同元素

	給定三個含有n個元素的整型數組a,b和c，求他們最小的共同元素。

	分析

	如果三個數組都有序，那么可以設置三個指針指向三個數組的頭部，然后根據這三個指針所指的值進行比較來移動指針，直道找到共同元素。

	代碼

	
//三個數組的共同元素-只找最小的
voidFindCommonElements(inta[],intb[],intc[],intx,inty,intz)
{
for(inti=0,j=0,k=0;i=b[j]
{
if(b[j]=c[k]
{
if(c[k]=a[i]
{
cout<

	

	如果三個數組都無序，可以先對a, b進行排序，然后對c中任意一個元素都在b和c中做二分搜索。

	代碼

	
//找出三個數組的共同元素
//O(NlogN)
intUniqueCommonItem(int*a,int*b,int*c,intn)
{
//sortarraya
qsort(a,n,sizeof(int),compare);//NlogN

//sortarrayb
qsort(b,n,sizeof(int),compare);//NlogN

//foreachelementinarrayc,doabinarysearchinaandb
//ThisisuptoacomplexityofN*2*logN
for(inti=0;i

	

	也可以對a進行排序，然后對于b和c中任意一個元素都在a中進行二分搜索，但是這樣做是有問題的，你看出來了么？感謝網友yy_5533指正。

	代碼

	
//找出三個數組唯一的共同元素
//O(NlogN)
intUniqueCommonItem1(int*a,int*b,int*c,intn)
{
//sortarraya
qsort(a,n,sizeof(int),compare);//NlogN

//Spacefortime
bool*bb=newbool[n];
memset(bb,0,n);

bool*bc=newbool[n];
memset(bb,0,n);

//foreachelementinb,doaBSinaandmarkallthecommonelement
for(inti=0;i

	

	排序和二分搜索代碼如下

	
//Determinewhetheracontainsvaluek
boolBinarySearch(int*a,intn,intk)
{
intleft=0;
intright=n-1;
while(left<=?right)
????{
????????int?mid?=?(left?+?right)?;

????????if(a[mid]?

	

	小小總結一下，對于在數組中進行查找的問題，可以分如下兩種情況處理

	如果給定的數組有序，那么首先應該想到Binary Search，所需O(logn)

	如果給定的數組無序，那么首先應該想到對數組進行排序，很多排序算法都能在O(nlogn)時間內對數組進行排序，然后再使用二分搜索，總的時間復雜度仍是O(nlogn)。

	如果能做到以上兩點，大多數關于數組的查找問題，都能迎刃而解。

	找出數組中唯一的重復元素

	給定含有1001個元素的數組，其中存放了1-1000之內的整數，只有一個整數是重復的，請找出這個數

	分析

	求出整個數組的和，再減去1-1000的和

	代碼

	略

	找出出現奇數次的元素

	給定一個含有n個元素的整型數組a，其中只有一個元素出現奇數次，找出這個元素。這道題實際上是一個變種，原題是找出數組中唯一一個出現一次的元素，下面的方法可以同時解決這兩道提。所以題目就用這個廣義的吧。

	分析

	因為對于任意一個數k，有k ^ k = 0，k ^ 0 = k，所以將a中所有元素進行異或，那么個數為偶數的元素異或后都變成了0，只留下了個數為奇數的那個元素。

	代碼

	
intFindElementWithOddCount(int*a,intn)
{
intr=a[0];

for(inti=1;i

	

	求數組中滿足給定和的數對

	給定兩個有序整型數組a和b，各有n個元素，求兩個數組中滿足給定和的數對，即對a中元素i和b中元素j，滿足i + j = d(d已知)

	分析

	兩個指針i和j分別指向數組的首尾，然后從兩端同時向中間遍歷。

	代碼

	
//找出滿足給定和的數對
voidFixedSum(int*a,int*b,intn,intd)
{
for(inti=0,j=n-1;i=0)
{
if(a[i]+b[j]d
--j;
}
}


	

	最大子段和

	給定一個整型數組a，求出最大連續子段之和，如果和為負數，則按0計算，比如1， 2， -5， 6， 8則輸出6 + 8 = 14

	分析

	編程珠璣上的經典題目，不多說了。

	代碼

	
//子數組的最大和
intSum(int*a,intn)
{
intcurSum=0;
intmaxSum=0;
for(inti=0;i

	

	最大子段積

	給定一個整型數組a，求出最大連續子段的乘積，比如 1， 2， -8， 12， 7則輸出12 * 7 = 84

	分析

	與最大子段和類似，注意處理負數的情況

	代碼

	
//子數組的最大乘積
intMaxProduct(int*a,intn)
{
intmaxProduct=1;//maxpositiveproductatcurrentposition
intminProduct=1;//minnegativeproductatcurrentposition
intr=1;//result,maxmultiplicationtotally

for(inti=0;i0)
{
maxProduct*=a[i];
minProduct=min(minProduct*a[i],1);
}
elseif(a[i]==0)
{
maxProduct=1;
minProduct=1;
}
else//a[i]

	

	數組循環移位

	將一個含有n個元素的數組向右循環移動k位，要求時間復雜度是O(n)，且只能使用兩個額外的變量，這是在微軟的編程之美上看到的一道題

	分析

	比如數組 1 2 3 4循環右移1位 將變成 4 1 2 3， 觀察可知1 2 3 的順序在移位前后沒有改變，只是和4的位置交換了一下，所以等同于1 2 3 4 先劃分為兩部分

	1 2 3 | 4，然后將1 2 3逆序，再將4 逆序 得到 3 2 1 4，最后整體逆序 得到 4 1 2 3

	代碼

	
//將buffer中start和end之間的元素逆序
voidReverse(intbuffer[],intstart,intend)
{
while(start

	

	稍微擴展一下,如果允許分配額外的數組,那么定義一個新的數組,然后將移位后的元素直接存入即可,也可以使用隊列,將移動后得元素出對,再插入隊尾即可.

	字符串逆序

	給定一個含有n個元素的字符數組a，將其原地逆序。

	分析

	可能您覺得這不是關于數組的，而是關于字符串的。是的。但是別忘了題目要求的是原地逆序，也就是不允許額外分配空間，那么參數肯定是字符數組形式，因為字符串是不能被修改的（這里只C/C++中的字符串常量）。

	所以，和數組有關了吧，只不過不是整型數組，而是字符數組。用兩個指針分別指向字符數組的首位，交換其對應的字符，然后兩個指針分別向數組中央移動，直到交叉。

	代碼

	
//字符串逆序
voidReverse(char*a,intn)
{
intleft=0;
intright=n-1;

while(left

	

	組合問題

	給定一個含有n個元素的整型數組a，從中任取m個元素，求所有組合。比如下面的例子

	a = 1, 2, 3, 4, 5

	m = 3

	輸出

	
123,124,125,134,135,145

234,235,245
345


	

	分析

	典型的排列組合問題，首選回溯法，為了簡化問題，我們將a中n個元素值分別設置為1-n

	代碼

	
//n選m的所有組合
intbuffer[100];

voidPrintArray(int*a,intn)
{
for(inti=0;i=value)
returnfalse;
}
returntrue;
}

voidSelect(intt,intn,intm)
{
if(t==m)
PrintArray(buffer,m);
else
{
for(inti=1;i<=?n;?i++)
????????{
????????????buffer[t]?=?i;
????????????if?(IsValid(t,?i))
????????????????Select(t?+?1,?n,?m);
????????}
????}
}


	

	合并兩個數組

	給定含有n個元素的兩個有序（非降序）整型數組a和b。合并兩個數組中的元素到整型數組c，要求去除重復元素并保持c有序（非降序）。例子如下

	a = 1, 2, 4, 8

	b = 1, 3, 5, 8

	c = 1, 2, 3, 4, 5, 8

	分析

	利用合并排序的思想，兩個指針i,j和k分別指向數組a和b，然后比較兩個指針對應元素的大小，有以下三種情況

	a[i] < b[j]，則c[k] = a[i]。

	a[i] == b[j]，則c[k]等于a[i]或b[j]皆可。

	a[i] > b[j]，則c[k] = b[j]。

	重復以上過程，直到i或者j到達數組末尾，然后將剩下的元素直接copy到數組c中即可

	代碼

	
//合并兩個有序數組
voidMerge(int*a,int*b,int*c,intn)
{
inti=0;
intj=0;
intk=0;

while(ib[j]//如果b中元素小，則插入b中元素到c
{
c[k++]=b[j];
++j;
}
}

if(i==n)//若a遍歷完畢，處理b中剩下的元素
{
for(intm=j;m

	

	重排問題

	給定含有n個元素的整型數組a，其中包括0元素和非0元素，對數組進行排序，要求：

	排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相對位置不變

	不能使用額外存儲空間

	例子如下

	
輸入0,3,0,2,1,0,0

輸出0,0,0,0,3,2,1


	

	分析

	此排序非傳統意義上的排序，因為它要求排序前后非0元素的相對位置不變，或許叫做整理會更恰當一些。我們可以從后向前遍歷整個數組，遇到某個位置i上的元素是非0元素時，如果a[k]為0，則將a[i]賦值給a[k]，a[k]賦值為0。實際上i是非0元素的下標，而k是0元素的下標

	代碼

	
voidArrange(int*a,intn)
{
intk=n-1;
for(inti=n-1;i>=0;--i)
{
if(a[i]!=0)
{
if(a[k]==0)
{
a[k]=a[i];
a[i]=0;
}
--k;
}
}
}


	

	找出絕對值最小的元素

	給定一個有序整數序列（非遞減序），可能包含負數，找出其中絕對值最小的元素，比如給定序列 -5, -3, -1, 2, 8 則返回1。

	分析

	由于給定序列是有序的，而這又是搜索問題，所以首先想到二分搜索法，只不過這個二分法比普通的二分法稍微麻煩點，可以分為下面幾種情況

	如果給定的序列中所有的數都是正數，那么數組的第一個元素即是結果。

	如果給定的序列中所有的數都是負數，那么數組的最后一個元素即是結果。

	如果給定的序列中既有正數又有負數，那么絕對值得最小值一定出現在正數和負數的連接處。

	為什么？

	因為對于負數序列來說，右側的數字比左側的數字絕對值小，如上面的-5, -3, -1, 而對于整整數來說，左邊的數字絕對值小，比如上面的2, 8，將這個思想用于二分搜索，可先判斷中間元素和兩側元素的符號，然后根據符號決定搜索區間，逐步縮小搜索區間，直到只剩下兩個元素。

	代碼

	單獨設置一個函數用來判斷兩個整數的符號是否相同。

	
boolSameSign(inta,intb)
{
if(a*b>0)
returntrue;
else
returnfalse;
}


	

	主函數代碼。

	
//找出一個非遞減序整數序列中絕對值最小的數
intMinimumAbsoluteValue(int*a,intn)
{
//Onlyonenumberinarray
if(n==1)
{
returna[0];
}

//Allnumbersinarrayhavethesamesign
if(SameSign(a[0],a[n-1]))
{
returna[0]>=0?a[0]:a[n-1];
}

//Binarysearch
intl=0;
intr=n-1;

while(l

	

	這段代碼是有問題的，感謝網友lingyunfish的指正，你看出來了么？修改后的代碼如下：

	
//找出一個非遞減序整數序列中絕對值最小的數
intMinimumAbsoluteValue(int*a,intn)
{
//Onlyonenumberinarray
if(n==1)
{
returna[0];
}

//Allnumbersinarrayhavethesamesign
if(SameSign(a[0],a[n-1]))
{
returna[0]>=0?a[0]:a[n-1];
}

//Binarysearch
intl=0;
intr=n-1;

while(l

	

	   審核編輯：彭靜