關(guān)注、星標(biāo)公眾號(hào)，直達(dá)精彩內(nèi)容

來源：嵌入式大雜燴

整理：李肖遙

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

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

數(shù)組求和

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

分析

簡單說一下，兩種情況

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和minValue
void?MaxandMin(int?*a,?int?l,?int?r,?int