用递归找到两个元素之间的最小差异

Question

我正在尝试制作“一维的最短距离算法”。

但是，我对递归的情况感到困惑。我不知道如何在递归调用后取回值（第 14 和 15 行）。我该如何修复以下代码？

def recCPairDist(points):
    if len(points) == 1:
        return 0
    elif len(points)== 2:
        abs(points[1]-points[0])
        #how do i assign the result final value back to "leftDist rightDist"
        #since its a recurisive, the result can be more than 1, should i store all the result in a list first?
        #then get the min(list)?

    else:
        mid = len(points) // 2
        first_half = points[:mid]
        second_half = points[mid:]
        leftDist = recCPairDist(first_half)
        rightDist = recCPairDist(second_half)
        midDist = abs(second_half[0] - first_half[1]) #i dont think this is correct since i didnt consider the recursion
        return min(leftDist,rightDist,midDist)

def cPairDist(points):
    points.sort()
    return recCPairDist(points)

P1 = [7, 4, 12, 14, 2, 10, 16, 6]

cPairDist(P1)

P1 的预期结果应该是 1，因为最短距离在 7 到 6 之间。

Answer 1

你真的很接近！您必须做三件事：

对于只有一点需要考虑的情况，你应该而不是return0。例如，对于数组 [3, 6, 9]，答案是 3，但您给定的基本情况将是 return 0。这是因为 odd-length 数组的结果子数组之一的长度为 1，并且当您从每个递归调用中 return 时，零 return 值将传播。
您需要 return len == 2 基本案例中的值 abs(points[1]-points[0]) 显式使用 return 关键字。
对于您的递归情况，最小差异必须在左半部分的两个连续元素之间，右半部分的两个连续元素之间，或者上半部分的最后一个元素和下半部分的第一个元素之间 (原始数组中的两个连续元素，但未包含在两个递归情况中）。所以，你的 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)

用递归找到两个元素之间的最小差异

Finding the minimum difference between two elements with recursion

python

algorithm

recursion