递归解决数组面试题：求和、找最值

"常见数组面试题" 在面试中，数组相关的题目经常被用来考察候选人的算法基础和逻辑思维能力。以下是一些常见的数组面试题及其解题思路： 1. **数组求和**： 该问题要求使用递归并只用一行代码来计算数组的总和。提供的代码实现如下： ```cpp int sum(int* a, int n) { return n == 0 ? 0 : sum(a, n - 1) + a[n - 1]; } ``` 这个函数通过递归的方式，每次将数组最后一个元素加到前n-1个元素的和上，直到n为0时递归结束。 2. **求数组的最大值和最小值**： 这里采用分治策略，递归地将数组分为左右两部分，直到子数组只剩下一个或两个元素。当数组只剩一个元素时，最大值和最小值都为该元素；当有二个元素时，根据它们的大小确定最大值和最小值。代码如下： ```cpp void MaxAndMin(int* a, int l, int r, int& maxValue, int& minValue) { if (l == r) { // 只有一个元素 maxValue = a[l]; minValue = a[l]; } else if (l + 1 == r) { // 有两个元素 if (a[l] >= a[r]) { maxValue = a[l]; minValue = a[r]; } else { maxValue = a[r]; minValue = a[l]; } } else { int m = (l + r) / 2; // 找中点 int leftMax, leftMin; MaxAndMin(a, l, m, leftMax, leftMin); // 递归计算左半部分 int rightMax, rightMin; MaxAndMin(a, m + 1, r, rightMax, rightMin); // 递归计算右半部分 maxValue = max(leftMax, rightMax); minValue = min(leftMin, rightMin); } } ``` 3. **求数组的最大值和次大值**： 同理，我们可以采用类似的方法，分别找出左右子数组的最大值和次大值，然后进行比较。关键在于如何处理最大值和次大值的关系，以及避免重复比较。 4. **求数组中出现次数超过一半的元素**： 这个问题可以通过摩尔投票法（Majority Voting Algorithm）解决，该方法通过统计元素出现的正负票数来找到多数元素。初始化一个计数器为1，一个候选值为数组的第一个元素。遍历数组，遇到相同元素时计数器加1，遇到不同元素时计数器减1，但计数器不会变为负数。最后返回的候选值就是出现次数超过一半的元素。 这些面试题主要涉及到递归、分治策略、线性扫描等基本算法思想，以及对数组特性的理解。在解答时，应注重代码的简洁性和效率，同时考虑边界条件和特殊情况的处理。熟悉这些题目的解法有助于提升在面试中的表现。