algorithm - 如何处理包含偶数个元素的子集？(使用分而治之找到峰值问题)

Question

我很难用分而治之算法编写代码。最大的问题是我不知道如何处理具有偶数个元素的子集。

一个典型的问题是“给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到一个峰值元素并返回它的索引”。

书上的算法说:

如果 nums[n/2] < nums[n/2 -1] 则只看左半边找到峰值

Else if nums[n/2] < nums[n/2 + 1] then only looking right half to find a peak

否则n/2位置是峰

当n = 2时，我不知道如何处理n/2。因为算法似乎总是将集合分成2部分。当子集包含奇数个元素时很容易理解，比如 [a,b,c]。我可以找到中间的元素 b 并进行比较。当子集只包含两个元素时，比如 [a, b]。我找不到要比较的中间元素。

为了使递归正确终止，我在 python 代码中添加了一些逻辑。我就是不能一次完成。我想知道在我的问题中是否有一种方法可以考虑关于像 [a,b] 这样的子集的终止条件？

class Solution:
def findPeakElement(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    def finder(start, end):
        if start == end:
            return start
        if end - start == 1:
            return end if nums[start] < nums[end] else start
        N = end-start+1
        if(nums[start+N//2]<nums[start+N//2-1]):
            return finder(start,start+N//2-1)
        elif(nums[start+N//2]<nums[start+N//2+1]):
            return finder(start+N//2+1,end)
        else:
            return start+N//2

    return finder(0,len(nums)-1)

Answer 1

我建议简化您的逻辑和样式，以便更容易推理您的代码。您正在重复计算 N//2 ，这会浪费周期并且噪音大且在语义上毫无意义。将工作保存在函数开头的名为 mid 的变量中，赋予它意义。在您的代码中添加间距以减少视觉噪音并使单步执行变得愉快(并且可能)。

至于start、end和N，这是一个额外的变量，需要考虑和操作--start 和 end 足以处理所有情况，混淆这些变量似乎是您代码中的一个问题。

由于您已经了解算法，因此您已接近解决方案。数组的奇偶性不是问题，但 - 唯一的问题是(字面意思!)当 mid == 0 和 mid == len(nums) - 1。在这两种情况下，只有一个邻居，所以如果我们分别尝试 nums[mid-1] 和 nums[mid+1] 就会崩溃。解决这些问题是在尝试这些比较之前测试 mid 不在数组的一端或另一端。

将所有这些放在一起，函数中需要发生的所有事情是:

def finder(start, end):
    mid = (start + end) // 2

    if mid > 0 and nums[mid] < nums[mid-1]:
        return finder(start, mid - 1)
    elif mid < end and nums[mid] < nums[mid+1]:
        return finder(mid + 1, end)
    else:
        return mid