關注、星標公眾號，直達精彩內(nèi)容

來源：嵌入式大雜燴

整理：李肖遙

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

• 數(shù)組求和
• 求數(shù)組的最大值和最小值
• 求數(shù)組的最大值和次大值
• 求數(shù)組中出現(xiàn)次數(shù)超過一半的元素
• 求數(shù)組中元素的最短距離
• 求兩個有序數(shù)組的共同元素
• 求三個數(shù)組的共同元素
• 找出數(shù)組中唯一的重復元素
• 找出出現(xiàn)奇數(shù)次的元素
• 求數(shù)組中滿足給定和的數(shù)對
• 最大子段和
• 最大子段積
• 數(shù)組循環(huán)移位
• 字符串逆序
• 組合問題
• 合并兩個數(shù)組
• 重排問題
• 找出絕對值最小的元素

數(shù)組求和

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

分析

簡單說一下，兩種情況

1. 如果數(shù)組元素個數(shù)為0，那么和為0。

2. 如果數(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ù)組分成左右兩部分，先求出左半部份的最大值和最小值，再求出右半部份的最大值和最小值，然后綜合起來求總體的最大值及最小值。

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

代碼

//?求數(shù)組的最大值和最小值，返回值在maxValue和minValue
void?MaxandMin(int?*a,?int?l,?int?r,?int