python - 分而治之策略python

Question

我正在尝试编写一个代码来比较列表的每个元素，并在两个方向上为壁橱的索引提供更大的数字:左或右。使用分治法

For example:

Input: arr=[5,2,6,8,1,4,3,9]
Output:
Left=[None, 0, None, None, 3, 3, 5, None]
Right=[2, 2, 3, 7, 5, 7, 7, None]

Input: arr=[4,2,3,1,8,5,6,9]
Output:
L=[None, 0, 0, 2, None, 4, 4, None]
R=[4, 2, 4, 4, 7, 6, 7, None]

这是我现在拥有的:

arr = [5,2,6,8,1,4,3,9]
def Left(arr):
    L = []
    for i in range(len(arr)):
        flag = True
        for j in range(i,-1,-1):
            if (arr[i] < arr[j]):
                L.append(j)
                flag = False
                break
        if flag:
            L.append(None)
    return L

def Right(arr):
    R = []
    for i in range(len(arr)):
        flag = True
        for j in range(i, len(arr), 1):
            if (arr[i] < arr[j]):
                R.append(j)
                flag = False
                break
        if flag:
                R.append(None)
    return R

print(*Left(arr), sep = ",")
print(*Right(arr), sep =",")

我的做法是否正确？谢谢。

Answer 1

这是我的“最接近的大右”版本算法的 python 版本代码。
显然，如您所见，它是递归的。递归真的很优雅但有点棘手，因为几行代码浓缩了很多关于算法设计和它们编码的语言的概念。在我看来，有 4 个相关时刻正在发生:

• 1) 递归调用。函数是对自身的调用。在此步骤中，列表可进步切片分成两半。一旦达到原子单元，将首先对它们执行基本算法(步骤 3)。如果未达到解决方案，则更大的列表大小将参与进一步递归的计算。
• 2) 终止条件。上一步不会永远运行，它允许停止递归并转到下一步(基本算法)。现在代码有 len(arr) > 1: 这意味着原子单元将是数字对(如果是奇数列表，则为三个数字之一)。您可以增加数量，以便递归函数在切片列表和汇总结果时停留更少的时间，但对应的是，在并行化环境中，“工作人员”将不得不消化更大的列表。
• 3) 基础算法。它进行必要的计算。无论列表的大小如何，它都会将其元素的索引返回到最接近右侧的较大数字
• 4) “计算保存”。基本算法不需要计算在先前递归中解析的那些数字的索引。一旦数字获得当前递归列表中的索引，还有一个 break 停止计算。

可以设计其他算法模型，当然效率更高。我想到了基于字典或不同切片策略的方法。

def closest_larger_right(arr):

    len_total = len(arr)
    result = [None] * len_total

    def recursive(arr, len_total, position=0):

        # 2) Termination condition
        if len(arr) > 1:

            mid = len(arr) // 2
            left = arr[:mid]
            right = arr[mid:]

            position_left = 0 + position
            position_right = len(left) + position

            # 1) Recursive calls
            recursive(left, len_total, position_left)
            recursive(right, len_total, position_right)

            # 3) Base algorithm
            for i in range(len(arr)-1):
                # 4) Calculation saving
                if result[i + position] is None:
                    for j in range(i+1, len(arr), 1):
                        if (arr[i] < arr[j]):
                            result[i + position] = j + position
                            break
            return result

    return recursive(arr, len_total)

# output: [2, 2, 3, 7, 5, 7, 7, None]
print(closest_larger_right([5, 2, 6, 8, 1, 4, 3, 9]))