電子發(fā)燒友App
數(shù)組是最基本的數(shù)據(jù)結(jié)構(gòu)，關(guān)于數(shù)組的面試題也屢見不鮮，本文羅列了一些常見的面試題，僅供參考。目前有以下18道題目。
數(shù)組求和
求數(shù)組的最大值和最小值
求數(shù)組的最大值和次大值
求數(shù)組中出現(xiàn)次數(shù)超過一半的元素
求數(shù)組中元素的最短距離
求兩個有序數(shù)組的共同元素
求三個數(shù)組的共同元素
找出數(shù)組中唯一的重復(fù)元素
找出出現(xiàn)奇數(shù)次的元素
求數(shù)組中滿足給定和的數(shù)對
最大子段和
最大子段積
數(shù)組循環(huán)移位
字符串逆序
組合問題
合并兩個數(shù)組
重排問題
找出絕對值最小的元素
數(shù)組求和
給定一個含有n個元素的整型數(shù)組a，求a中所有元素的和。可能您會覺得很簡單，是的，的確簡單，但是為什么還要說呢，原因有二，第一，這道題要求用遞歸法，只用一行代碼。第二，這是我人生中第一次面試時候遇到的題，意義特殊。
分析
簡單說一下，兩種情況
如果數(shù)組元素個數(shù)為0，那么和為0。
如果數(shù)組元素個數(shù)為n，那么先求出前n - 1個元素之和，再加上a[n - 1]即可
代碼
?
//?數(shù)組求和
int?sum(int*a,?int?n)
{
???return?n?==?0???0?:?sum(a,?n?-1)?+?a[n?-1];
}
?
求數(shù)組的最大值和最小值
給定一個含有n個元素的整型數(shù)組a，找出其中的最大值和最小值
分析
常規(guī)的做法是遍歷一次，分別求出最大值和最小值，但我這里要說的是分治法(Divide and couquer)，將數(shù)組分成左右兩部分，先求出左半部份的最大值和最小值，再求出右半部份的最大值和最小值，然后綜合起來求總體的最大值及最小值。
這是個遞歸過程，對于劃分后的左右兩部分，同樣重復(fù)這個過程，直到劃分區(qū)間內(nèi)只剩一個元素或者兩個元素。
代碼
?
//?求數(shù)組的最大值和最小值，返回值在maxValue和minValue
void?MaxandMin(int?*a,?int?l,?int?r,?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?;
????}
????int?m?=?(l?+?r)?/?2?;?//?求中點
????int?lmax?;?//?左半部份最大值
????int?lmin?;?//?左半部份最小值
????MaxandMin(a,?l,?m,?lmax,?lmin)?;?//?遞歸計算左半部份
????int?rmax?;?//?右半部份最大值
????int?rmin?;?//?右半部份最小值
????MaxandMin(a,?m?+?1,?r,?rmax,?rmin)?;?//?遞歸計算右半部份
????maxValue?=?max(lmax,?rmax)?;?//?總的最大值
????minValue?=?min(lmin,?rmin)?;?//?總的最小值
}
?
求數(shù)組的最大值和次大值
給定一個含有n個元素的整型數(shù)組，求其最大值和次大值
分析
思想和上一題類似，同樣是用分治法，先求出左邊的最大值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。感謝網(wǎng)友 從無到有靠誰人 指出。
代碼
?
//?找出數(shù)組的最大值和次大值，a是待查找的數(shù)組，left和right是查找區(qū)間，max和second存放結(jié)果
void?MaxandMin(int?a[],?int?left,?int?right,?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?
?
求數(shù)組中出現(xiàn)次數(shù)超過一半的元素
給定一個n個整型元素的數(shù)組a，其中有一個元素出現(xiàn)次數(shù)超過n / 2，求這個元素。據(jù)說是百度的一道題
分析
設(shè)置一個當(dāng)前值和當(dāng)前值的計數(shù)器，初始化當(dāng)前值為數(shù)組首元素，計數(shù)器值為1，然后從第二個元素開始遍歷整個數(shù)組，對于每個被遍歷到的值a[i]
1 如果a[i]==currentValue，則計數(shù)器值加1
2 如果a[i] != currentValue， 則計數(shù)器值減1，如果計數(shù)器值小于0，則更新當(dāng)前值為a[i]，并將計數(shù)器值重置為1
代碼
?
//?找出數(shù)組中出現(xiàn)次數(shù)超過一半的元素
int?Find(int*?a,?int?n)
{
????int?curValue?=?a[0]?;
????int?count?=?1?;
????for?(int?i?=?1;?i?
?
另一個方法是先對數(shù)組排序，然后取中間元素即可，因為如果某個元素的個數(shù)超過一半，那么數(shù)組排序后該元素必定占據(jù)數(shù)組的中間位置。
求數(shù)組中元素的最短距離
給定一個含有n個元素的整型數(shù)組，找出數(shù)組中的兩個元素x和y使得abs(x - y)值最小
分析
先對數(shù)組排序，然后遍歷一次即可
代碼
?
int?compare(const?void*?a,?const?void*?b)
{
????return?*(int*)a?-?*(int*)b?;
}
//?求數(shù)組中元素的最短距離
void?MinimumDistance(int*?a,?int?n)
{
????//?Sort
????qsort(a,?n,?sizeof(int),?compare)?;
????int?i?;?//?Index?of?number?1
????int?j?;?//?Index?of?number?2
????int?minDistance?=?numeric_limits::max()?;
????for?(int?k?=?0;?k?
?
求兩個有序數(shù)組的共同元素
給定兩個含有n個元素的有序（非降序）整型數(shù)組a和b，求出其共同元素，比如
a = 0, 1, 2, 3, 4
b = 1, 3, 5, 7, 9
輸出 1, 3
分析
充分利用數(shù)組有序的性質(zhì)，用兩個指針i和j分別指向a和b，比較a[i]和b[j]，根據(jù)比較結(jié)果移動指針，則有如下三種情況
a[i] < b[j]，則i增加1，繼續(xù)比較
a[i] == b[j]，則i和j皆加1，繼續(xù)比較
a[i] < b[j]，則j加1，繼續(xù)比較
重復(fù)以上過程直到i或j到達(dá)數(shù)組末尾。
代碼
?
//?找出兩個數(shù)組的共同元素
void?FindCommon(int*?a,?int*?b,?int?n)
{
????int?i?=?0;
????int?j?=?0?;
????while?(i??b[j]
????????????++j?;
????}
}
?
這到題還有其他的解法，比如對于a中任意一個元素，在b中對其進行Binary Search，因為a中有n個元素，而在b中進行Binary Search需要logn。所以找出全部相同元素的時間復(fù)雜度是O(nlogn)。
另外，上面的方法，只要b有序即可，a是否有序無所謂，因為我們只是在b中做Binary Search。
如果a也有序的話，那么再用上面的方法就有點慢了，因為如果a中某個元素在b中的位置是k的話，那么a中下一個元素在b中的位置一定位于k的右側(cè)，所以本次的搜索空間可以根據(jù)上次的搜索結(jié)果縮小，而不是仍然在整個b中搜索。也即如果a和b都有序的話，代碼可以做如下修改，記錄上次搜索時b中元素的位置，作為下一次搜索的起始點。
求三個數(shù)組的共同元素
給定三個含有n個元素的整型數(shù)組a,b和c，求他們最小的共同元素。
分析
如果三個數(shù)組都有序，那么可以設(shè)置三個指針指向三個數(shù)組的頭部，然后根據(jù)這三個指針?biāo)傅闹颠M行比較來移動指針，直道找到共同元素。
代碼
?
//?三個數(shù)組的共同元素-只找最小的
void?FindCommonElements(int?a[],?int?b[],?int?c[],?int?x,?int?y,?int?z)
{
????for(int?i?=?0,?j?=?0,?k?=?0;?i?=?b[j]
????????{
????????????if(b[j]?=?c[k]
????????????{
????????????????if(c[k]?=?a[i]
????????????????{
????????????????????cout?<
?
如果三個數(shù)組都無序，可以先對a, b進行排序，然后對c中任意一個元素都在b和c中做二分搜索。
代碼
?
//?找出三個數(shù)組的共同元素
//?O(NlogN)
int?UniqueCommonItem(int?*a,?int?*b,?int?*c,?int?n)
{
????//?sort?array?a
????qsort(a,?n,?sizeof(int),?compare)?;?//?NlogN
????//?sort?array?b
????qsort(b,?n,?sizeof(int),?compare)?;?//?NlogN
????//?for?each?element?in?array?c,?do?a?binary?search?in?a?and?b
????//?This?is?up?to?a?complexity?of?N*2*logN
????for?(int?i?=?0;?i?
?
也可以對a進行排序，然后對于b和c中任意一個元素都在a中進行二分搜索，但是這樣做是有問題的，你看出來了么？感謝網(wǎng)友yy_5533指正。
代碼
?
//?找出三個數(shù)組唯一的共同元素
//?O(NlogN)
int?UniqueCommonItem1(int?*a,?int?*b,?int?*c,?int?n)
{
????//?sort?array?a
????qsort(a,?n,?sizeof(int),?compare)?;?//?NlogN
????//?Space?for?time
????bool?*bb?=?new?bool[n]?;
????memset(bb,?0,?n)?;
????bool?*bc?=?new?bool[n]?;
????memset(bb,?0,?n)?;
????//?for?each?element?in?b,?do?a?BS?in?a?and?mark?all?the?common?element
????for?(int?i?=?0;?i?
?
排序和二分搜索代碼如下
?
//?Determine?whether?a?contains?value?k
bool?BinarySearch(int?*a,?int?n,?int?k)
{
????int?left?=?0?;
????int?right?=?n?-?1?;
????while?(left?<=?right)
????{
????????int?mid?=?(left?+?right)?;
????????if(a[mid]?
?
小小總結(jié)一下，對于在數(shù)組中進行查找的問題，可以分如下兩種情況處理
如果給定的數(shù)組有序，那么首先應(yīng)該想到Binary Search，所需O(logn)
如果給定的數(shù)組無序，那么首先應(yīng)該想到對數(shù)組進行排序，很多排序算法都能在O(nlogn)時間內(nèi)對數(shù)組進行排序，然后再使用二分搜索，總的時間復(fù)雜度仍是O(nlogn)。
如果能做到以上兩點，大多數(shù)關(guān)于數(shù)組的查找問題，都能迎刃而解。
找出數(shù)組中唯一的重復(fù)元素
給定含有1001個元素的數(shù)組，其中存放了1-1000之內(nèi)的整數(shù)，只有一個整數(shù)是重復(fù)的，請找出這個數(shù)
分析
求出整個數(shù)組的和，再減去1-1000的和
代碼
略
找出出現(xiàn)奇數(shù)次的元素
給定一個含有n個元素的整型數(shù)組a，其中只有一個元素出現(xiàn)奇數(shù)次，找出這個元素。這道題實際上是一個變種，原題是找出數(shù)組中唯一一個出現(xiàn)一次的元素，下面的方法可以同時解決這兩道提。所以題目就用這個廣義的吧。
分析
因為對于任意一個數(shù)k，有k ^ k = 0，k ^ 0 = k，所以將a中所有元素進行異或，那么個數(shù)為偶數(shù)的元素異或后都變成了0，只留下了個數(shù)為奇數(shù)的那個元素。
代碼
?
int?FindElementWithOddCount(int*a,?int?n)
{
???int?r?=?a[0]?;
???for?(int?i?=1;?i?
?
求數(shù)組中滿足給定和的數(shù)對
給定兩個有序整型數(shù)組a和b，各有n個元素，求兩個數(shù)組中滿足給定和的數(shù)對，即對a中元素i和b中元素j，滿足i + j = d(d已知)
分析
兩個指針i和j分別指向數(shù)組的首尾，然后從兩端同時向中間遍歷。
代碼
?
//?找出滿足給定和的數(shù)對
void?FixedSum(int*?a,?int*?b,?int?n,?int?d)
{
????for?(int?i?=?0,?j?=?n?-?1;?i?=?0)
????{
????????if?(a[i]?+?b[j]??d
????????????--j?;
????}
}
?
最大子段和
給定一個整型數(shù)組a，求出最大連續(xù)子段之和，如果和為負(fù)數(shù)，則按0計算，比如1， 2， -5， 6， 8則輸出6 + 8 = 14
分析
編程珠璣上的經(jīng)典題目，不多說了。
代碼
?
//?子數(shù)組的最大和
int?Sum(int*?a,?int?n)
{
????int?curSum?=?0;
????int?maxSum?=?0;
????for?(int?i?=?0;?i?
?
最大子段積
給定一個整型數(shù)組a，求出最大連續(xù)子段的乘積，比如 1， 2， -8， 12， 7則輸出12 * 7 = 84
分析
與最大子段和類似，注意處理負(fù)數(shù)的情況
代碼
?
//?子數(shù)組的最大乘積
int?MaxProduct(int?*a,?int?n)
{
????int?maxProduct?=?1;?//?max?positive?product?at?current?position
????int?minProduct?=?1;?//?min?negative?product?at?current?position
????int?r?=?1;?//?result,?max?multiplication?totally
????for?(int?i?=?0;?i??0)
????????{
????????????maxProduct?*=?a[i];
????????????minProduct?=?min(minProduct?*?a[i],?1);
????????}
????????else?if?(a[i]?==?0)
????????{
????????????maxProduct?=?1;
????????????minProduct?=?1;
????????}
????????else?//?a[i]?
?
數(shù)組循環(huán)移位
將一個含有n個元素的數(shù)組向右循環(huán)移動k位，要求時間復(fù)雜度是O(n)，且只能使用兩個額外的變量，這是在微軟的編程之美上看到的一道題
分析
比如數(shù)組 1 2 3 4循環(huán)右移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之間的元素逆序
void?Reverse(?int?buffer[],?int?start,?int?end?)
{
????while?(?start?
?
稍微擴展一下,如果允許分配額外的數(shù)組,那么定義一個新的數(shù)組,然后將移位后的元素直接存入即可,也可以使用隊列,將移動后得元素出對,再插入隊尾即可.
字符串逆序
給定一個含有n個元素的字符數(shù)組a，將其原地逆序。
分析
可能您覺得這不是關(guān)于數(shù)組的，而是關(guān)于字符串的。是的。但是別忘了題目要求的是原地逆序，也就是不允許額外分配空間，那么參數(shù)肯定是字符數(shù)組形式，因為字符串是不能被修改的（這里只C/C++中的字符串常量）。
所以，和數(shù)組有關(guān)了吧，只不過不是整型數(shù)組，而是字符數(shù)組。用兩個指針分別指向字符數(shù)組的首位，交換其對應(yīng)的字符，然后兩個指針分別向數(shù)組中央移動，直到交叉。
代碼
?
//?字符串逆序
void?Reverse(char*a,?int?n)
{
???int?left?=0;
???int?right?=?n?-1;
???while?(left?
?
組合問題
給定一個含有n個元素的整型數(shù)組a，從中任取m個元素，求所有組合。比如下面的例子
a = 1, 2, 3, 4, 5
m = 3
輸出
?
1?2?3,?1?2?4,?1?2?5,?1?3?4,?1?3?5,?1?4?5
2?3?4,?2?3?5,?2?4?5
3?4?5
?
分析
典型的排列組合問題，首選回溯法，為了簡化問題，我們將a中n個元素值分別設(shè)置為1-n
代碼
?
//?n選m的所有組合
int?buffer[100]?;
void?PrintArray(int?*a,?int?n)
{
????for?(int?i?=?0;?i?=?value)
????????????return?false;
????}
????return?true;
}
void?Select(int?t,?int?n,?int?m)
{
????if?(t?==?m)
????????PrintArray(buffer,?m);
????else
????{
????????for?(int?i?=?1;?i?<=?n;?i++)
????????{
????????????buffer[t]?=?i;
????????????if?(IsValid(t,?i))
????????????????Select(t?+?1,?n,?m);
????????}
????}
}
?
合并兩個數(shù)組
給定含有n個元素的兩個有序（非降序）整型數(shù)組a和b。合并兩個數(shù)組中的元素到整型數(shù)組c，要求去除重復(fù)元素并保持c有序（非降序）。例子如下
a = 1, 2, 4, 8
b = 1, 3, 5, 8
c = 1, 2, 3, 4, 5, 8
分析
利用合并排序的思想，兩個指針i,j和k分別指向數(shù)組a和b，然后比較兩個指針對應(yīng)元素的大小，有以下三種情況
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]。
重復(fù)以上過程，直到i或者j到達(dá)數(shù)組末尾，然后將剩下的元素直接copy到數(shù)組c中即可
代碼
?
//?合并兩個有序數(shù)組
void?Merge(int?*a,?int?*b,?int?*c,?int?n)
{
????int?i?=?0?;
????int?j?=?0?;
????int?k?=?0?;
????while?(i??b[j]?//?如果b中元素小，則插入b中元素到c
????????{
????????????c[k++]?=?b[j]?;
????????????++j?;
????????}
????}
????if?(i?==?n)?//?若a遍歷完畢，處理b中剩下的元素
????{
????????for?(int?m?=?j;?m?
?
重排問題
給定含有n個元素的整型數(shù)組a，其中包括0元素和非0元素，對數(shù)組進行排序，要求：
排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相對位置不變
不能使用額外存儲空間
例子如下
?
輸入?0,?3,?0,?2,?1,?0,?0
輸出?0,?0,?0,?0,?3,?2,?1
?
分析
此排序非傳統(tǒng)意義上的排序，因為它要求排序前后非0元素的相對位置不變，或許叫做整理會更恰當(dāng)一些。我們可以從后向前遍歷整個數(shù)組，遇到某個位置i上的元素是非0元素時，如果a[k]為0，則將a[i]賦值給a[k]，a[k]賦值為0。實際上i是非0元素的下標(biāo)，而k是0元素的下標(biāo)
代碼
?
void?Arrange(int*?a,?int?n)
{
????int?k?=?n?-1?;
????for?(int?i?=?n?-1;?i?>=0;?--i)
????{
????????if?(a[i]?!=0)
????????{
????????????if?(a[k]?==0)
????????????{
????????????????a[k]?=?a[i]?;
????????????????a[i]?=0?;
????????????}
????????????--k?;
????????}
????}
}
?
找出絕對值最小的元素
給定一個有序整數(shù)序列（非遞減序），可能包含負(fù)數(shù)，找出其中絕對值最小的元素，比如給定序列 -5, -3, -1, 2, 8 則返回1。
分析
由于給定序列是有序的，而這又是搜索問題，所以首先想到二分搜索法，只不過這個二分法比普通的二分法稍微麻煩點，可以分為下面幾種情況
如果給定的序列中所有的數(shù)都是正數(shù)，那么數(shù)組的第一個元素即是結(jié)果。
如果給定的序列中所有的數(shù)都是負(fù)數(shù)，那么數(shù)組的最后一個元素即是結(jié)果。
如果給定的序列中既有正數(shù)又有負(fù)數(shù)，那么絕對值得最小值一定出現(xiàn)在正數(shù)和負(fù)數(shù)的連接處。
為什么？
因為對于負(fù)數(shù)序列來說，右側(cè)的數(shù)字比左側(cè)的數(shù)字絕對值小，如上面的-5, -3, -1, 而對于整整數(shù)來說，左邊的數(shù)字絕對值小，比如上面的2, 8，將這個思想用于二分搜索，可先判斷中間元素和兩側(cè)元素的符號，然后根據(jù)符號決定搜索區(qū)間，逐步縮小搜索區(qū)間，直到只剩下兩個元素。
代碼
單獨設(shè)置一個函數(shù)用來判斷兩個整數(shù)的符號是否相同。
?
bool?SameSign(int?a,?int?b)
{
????if?(a?*?b?>?0)
????????return?true;
????else
????????return?false;
}
?
主函數(shù)代碼。
?
//?找出一個非遞減序整數(shù)序列中絕對值最小的數(shù)
int?MinimumAbsoluteValue(int*?a,?int?n)
{
????//?Only?one?number?in?array
????if?(n?==1)
????{
????????return?a[0]?;
????}
????//?All?numbers?in?array?have?the?same?sign
????if?(SameSign(a[0],?a[n?-1]))
????{
????????return?a[0]?>=0??a[0]?:?a[n?-1]?;
????}
????//?Binary?search
????int?l?=0?;
????int?r?=?n?-1?;
????while(l?
?
這段代碼是有問題的，感謝網(wǎng)友lingyunfish的指正，你看出來了么？修改后的代碼如下：
?
//?找出一個非遞減序整數(shù)序列中絕對值最小的數(shù)
int?MinimumAbsoluteValue(int*?a,?int?n)
{
????//?Only?one?number?in?array
????if?(n?==1)
????{
????????return?a[0]?;
????}
????//?All?numbers?in?array?have?the?same?sign
????if?(SameSign(a[0],?a[n?-1]))
????{
????????return?a[0]?>=0??a[0]?:?a[n?-1]?;
????}
????//?Binary?search
????int?l?=0?;
????int?r?=?n?-1?;
????while(l?
?
審核編輯：湯梓紅
?
工商網(wǎng)監(jiān)
評論