分而治之战略

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]))

Answer 2

我不确定如何在这里应用分治算法，但这里有一个对当前算法的改进，对于数组中的n个元素，该算法的最佳运行时间为O（n）：

stack = []
left = []
for i in range(len(arr)):
    while stack and arr[stack[-1]] < arr[i]:
        stack.pop()
    left.append(stack[-1] if stack else None)
    stack.append(i)

这使用堆栈跟踪左侧较大元素的索引，只要它们的元素小于当前元素，就从堆栈中弹出索引，然后添加当前索引本身。由于每个元素最多只能添加到堆栈中并从堆栈中弹出一次，因此运行时间为O（n）。只需按相反顺序迭代数组，就可以对右侧元素使用相同的方法