一维最短距离递归算法

你真的很接近!你必须做三件事:

1. 对于只有一点要考虑的情况,你应该 不 回来 0 .例如,对于数组 [3, 6, 9] ,答案是3,但给定的基本情况将返回 0 。这是因为对于奇数长度数组,其中一个子数组的长度为1,当您从每个递归调用返回时,零返回值将传播。
2. 您需要返回值 abs(points[1]-points[0]) 在 len == 2 使用 return 关键词。
3. 对于递归情况,最小差值必须在左半部分的两个连续元素之间、右半部分的两个连续元素之间,或者在前半部分的最后一个元素和后半部分的第一个元素之间(原始数组中的两个连续元素,但在两个递归情况中不包括)。所以,你的 midDist 应计算此值。

下面是一段代码片段,它解决了这三个问题:

def recCPairDist(points):
    if len(points) == 1:
        return float('inf')
    elif len(points)== 2:
        return abs(points[1]-points[0])
    else:
        mid = len(points) // 2
        first_half = points[:mid]
        second_half = points[mid:]
        leftDist = recCPairDist(first_half)
        rightDist = recCPairDist(second_half)
        midDist = abs(first_half[-1] - second_half[0])
        return min(leftDist,rightDist,midDist)