數(shù)組是最基本的數(shù)據(jù)結(jié)構(gòu),關(guān)于數(shù)組的面試題也屢見不鮮,本文羅列了一些常見的面試題,僅供參考,如果您有更好的題目或者想法,歡迎留言討論。目前有以下18道題目,如果有好的題目,隨時(shí)更新。
數(shù)組求和
求數(shù)組的最大值和最小值
求數(shù)組的最大值和次大值
求數(shù)組中出現(xiàn)次數(shù)超過一半的元素
求數(shù)組中元素的最短距離
找出絕對(duì)值最小的元素
數(shù)組求和
給定一個(gè)含有n個(gè)元素的整型數(shù)組a,求a中所有元素的和。可能您會(huì)覺得很簡(jiǎn)單,是的,的確簡(jiǎn)單,但是為什么還要說呢,原因有二,第一,這道題要求用遞歸法,只用一行代碼。第二,這是我人生中第一次面試時(shí)候遇到的題,意義特殊。
分析
簡(jiǎn)單說一下,兩種情況
1. 如果數(shù)組元素個(gè)數(shù)為0,那么和為0。
2. 如果數(shù)組元素個(gè)數(shù)為n,那么先求出前n - 1個(gè)元素之和,再加上a[n - 1]即可
代碼
// 數(shù)組求和int sum(int*a, int n){ return n == 0 ? 0 : sum(a, n -1) + a[n -1];}
求數(shù)組的最大值和最小值
給定一個(gè)含有n個(gè)元素的整型數(shù)組a,找出其中的最大值和最小值
分析
常規(guī)的做法是遍歷一次,分別求出最大值和最小值,但我這里要說的是分治法(Divide and couquer),將數(shù)組分成左右兩部分,先求出左半部份的最大值和最小值,再求出右半部份的最大值和最小值,然后綜合起來求總體的最大值及最小值。這是個(gè)遞歸過程,對(duì)于劃分后的左右兩部分,同樣重復(fù)這個(gè)過程,直到劃分區(qū)間內(nèi)只剩一個(gè)元素或者兩個(gè)元素。
代碼
// 求數(shù)組的最大值和最小值,返回值在maxValue和minValuevoid MaxandMin(int *a, int l, int r, int& maxValue, int& minValue){ if(l == r) // l與r之間只有一個(gè)元素 { maxValue = a[l] ; minValue = a[l] ; return ; } if(l + 1 == r) // l與r之間只有兩個(gè)元素 { if(a[l] >= a[r]) { maxValue = a[l] ; minValue = a[r] ; } else { maxValue = a[r] ; minValue = a[l] ; } return ; } int m = (l + r) / 2 ; // 求中點(diǎn) int lmax ; // 左半部份最大值 int lmin ; // 左半部份最小值 MaxandMin(a, l, m, lmax, lmin) ; // 遞歸計(jì)算左半部份 int rmax ; // 右半部份最大值 int rmin ; // 右半部份最小值 MaxandMin(a, m + 1, r, rmax, rmin) ; // 遞歸計(jì)算右半部份 maxValue = max(lmax, rmax) ; // 總的最大值 minValue = min(lmin, rmin) ; // 總的最小值}
求數(shù)組的最大值和次大值
給定一個(gè)含有n個(gè)元素的整型數(shù)組,求其最大值和次大值
分析
思想和上一題類似,同樣是用分治法,先求出左邊的最大值leftmax和次大值leftsecond,再求出右邊的最大值rightmax和次大值rightsecond,然后合并,如何合并呢?分情況考慮
1 如果leftmax > rightmax,那么可以肯定leftmax是最大值,但次大值不一定是rightmax,但肯定不是rightsecond,只需將leftsecond與rightmax做一次比較即可。
2 如果rightmax > leftmax,那么可以肯定rightmax是最大值,但次大值不一定是leftmax,但肯定不是leftsecond,所以只需將leftmax與rightsecond做一次比較即可。
注意
這種方法無法處理最大元素有多個(gè)的情況,比如3,5,7,7將返回7,7而不是7,5。感謝網(wǎng)友從無到有靠誰(shuí)人指出。
代碼
// 找出數(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] < a[right] ? a[left] : a[right] ; } else { int mid = left + (right - left) /2 ; int leftmax ; int leftsecond ; MaxandMin(a, left, mid, leftmax, leftsecond) ; int rightmax ; int rightsecond ; MaxandMin(a, mid +1, right, rightmax, rightsecond) ; if (leftmax > rightmax) { max = leftmax ; second = leftsecond > rightmax ? leftsecond : rightmax ; } else { max = rightmax ; second = leftmax < rightsecond ? rightsecond : leftmax ; } }}
求數(shù)組中出現(xiàn)次數(shù)超過一半的元素
給定一個(gè)n個(gè)整型元素的數(shù)組a,其中有一個(gè)元素出現(xiàn)次數(shù)超過n / 2,求這個(gè)元素。據(jù)說是百度的一道題
分析
設(shè)置一個(gè)當(dāng)前值和當(dāng)前值的計(jì)數(shù)器,初始化當(dāng)前值為數(shù)組首元素,計(jì)數(shù)器值為1,然后從第二個(gè)元素開始遍歷整個(gè)數(shù)組,對(duì)于每個(gè)被遍歷到的值a[i]
1 如果a[i]==currentValue,則計(jì)數(shù)器值加1
2 如果a[i] != currentValue, 則計(jì)數(shù)器值減1,如果計(jì)數(shù)器值小于0,則更新當(dāng)前值為a[i],并將計(jì)數(shù)器值重置為1
代碼
// 找出數(shù)組中出現(xiàn)次數(shù)超過一半的元素int Find(int* a, int n){ int curValue = a[0] ; int count = 1 ; for (int i = 1; i < n; ++i) { if (a[i] == curValue) count++ ; else { count-- ; if (count < 0) { curValue = a[i] ; count = 1 ; } } } return curValue ;}
另一個(gè)方法是先對(duì)數(shù)組排序,然后取中間元素即可,因?yàn)槿绻硞€(gè)元素的個(gè)數(shù)超過一半,那么數(shù)組排序后該元素必定占據(jù)數(shù)組的中間位置。
求數(shù)組中元素的最短距離
給定一個(gè)含有n個(gè)元素的整型數(shù)組,找出數(shù)組中的兩個(gè)元素x和y使得abs(x - y)值最小
分析
先對(duì)數(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 < n - 1; ++k) { if (a[k + 1] - a[k] < minDistance) { minDistance = a[k + 1] - a[k] ; i = a[k] ; j = a[k + 1] ; } } cout << "Minimum distance is: " << minDistance << endl ; cout << "i = " << i << " j = " << j << endl ; }
找出絕對(duì)值最小的元素
給定一個(gè)有序整數(shù)序列(非遞減序),可能包含負(fù)數(shù),找出其中絕對(duì)值最小的元素,比如給定序列 -5, -3, -1, 2, 8 則返回1。
分析
由于給定序列是有序的,而這又是搜索問題,所以首先想到二分搜索法,只不過這個(gè)二分法比普通的二分法稍微麻煩點(diǎn),可以分為下面幾種情況
如果給定的序列中所有的數(shù)都是正數(shù),那么數(shù)組的第一個(gè)元素即是結(jié)果。
如果給定的序列中所有的數(shù)都是負(fù)數(shù),那么數(shù)組的最后一個(gè)元素即是結(jié)果。
如果給定的序列中既有正數(shù)又有負(fù)數(shù),那么絕對(duì)值得最小值一定出現(xiàn)在正數(shù)和負(fù)數(shù)的連接處。
為什么?因?yàn)閷?duì)于負(fù)數(shù)序列來說,右側(cè)的數(shù)字比左側(cè)的數(shù)字絕對(duì)值小,如上面的-5, -3, -1, 而對(duì)于整整數(shù)來說,左邊的數(shù)字絕對(duì)值小,比如上面的2, 8,將這個(gè)思想用于二分搜索,可先判斷中間元素和兩側(cè)元素的符號(hào),然后根據(jù)符號(hào)決定搜索區(qū)間,逐步縮小搜索區(qū)間,直到只剩下兩個(gè)元素。
代碼
單獨(dú)設(shè)置一個(gè)函數(shù)用來判斷兩個(gè)整數(shù)的符號(hào)是否相同
bool SameSign(int a, int b){ if (a * b > 0) return true; else return false;}
// 找出一個(gè)非遞減序整數(shù)序列中絕對(duì)值最小的數(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 < r) { if (l + 1 == r) { return abs(a[l]) < abs(a[r]) ? a[l] : a[r] ; } int m = (l + r) /2 ; if (SameSign(a[m], a[r])) { r = m; continue; } else { l = m ; continue; } }}
-
代碼
+關(guān)注
關(guān)注
30文章
4790瀏覽量
68649 -
數(shù)據(jù)結(jié)構(gòu)
+關(guān)注
關(guān)注
3文章
573瀏覽量
40137 -
數(shù)組
+關(guān)注
關(guān)注
1文章
417瀏覽量
25956
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
C語(yǔ)言中指針數(shù)組和數(shù)組指針的區(qū)別
一個(gè)一維數(shù)組怎么實(shí)現(xiàn)相鄰元素相減后求和?
VB數(shù)組的使用
關(guān)于 Java 數(shù)組的 12 個(gè)最佳方法
Java創(chuàng)建數(shù)組的幾種方式及區(qū)別
Keil使用結(jié)構(gòu)體數(shù)組的奇怪問題
![Keil使用結(jié)構(gòu)體<b class='flag-5'>數(shù)組</b>的奇怪問題](https://file.elecfans.com/web1/M00/D9/4E/pIYBAF_1ac2Ac0EEAABDkS1IP1s689.png)
評(píng)論