数组还能这么玩？

关注、星标公众号，直达精彩内容

来源：嵌入式大杂烩

整理：李肖遥

数组是最基本的数据结构，关于数组的面试题也屡见不鲜，本文罗列了一些常见的面试题，仅供参考。目前有以下18道题目。

• 数组求和
• 求数组的最大值和最小值
• 求数组的最大值和次大值
• 求数组中出现次数超过一半的元素
• 求数组中元素的最短距离
• 求两个有序数组的共同元素
• 求三个数组的共同元素
• 找出数组中唯一的重复元素
• 找出出现奇数次的元素
• 求数组中满足给定和的数对
• 最大子段和
• 最大子段积
• 数组循环移位
• 字符串逆序
• 组合问题
• 合并两个数组
• 重排问题
• 找出绝对值最小的元素

数组求和

给定一个含有n个元素的整型数组a，求a中所有元素的和。可能您会觉得很简单，是的，的确简单，但是为什么还要说呢，原因有二，第一，这道题要求用递归法，只用一行代码。第二，这是我人生中第一次面试时候遇到的题，意义特殊。

分析

简单说一下，两种情况

1. 如果数组元素个数为0，那么和为0。

2. 如果数组元素个数为n，那么先求出前n - 1个元素之和，再加上a[n - 1]即可

代码

// 数组求和
int sum(int*a, int n)
{
   return n == 0 ? 0 : sum(a, n -1)   a[n -1];
}


求数组的最大值和最小值

给定一个含有n个元素的整型数组a，找出其中的最大值和最小值

分析

常规的做法是遍历一次，分别求出最大值和最小值，但我这里要说的是分治法(Divide and couquer)，将数组分成左右两部分，先求出左半部份的最大值和最小值，再求出右半部份的最大值和最小值，然后综合起来求总体的最大值及最小值。

这是个递归过程，对于划分后的左右两部分，同样重复这个过程，直到划分区间内只剩一个元素或者两个元素。

代码

// 求数组的最大值和最小值，返回值在maxValue和minValue
void MaxandMin(int *a, int l, int r, int