产生最大差值的返回索引

问题描述 投票:1回答:2

我有一个递归函数,它可以找到任意两个整数之间的最大差,只要第二个索引处的值比第一个索引处的值higher

def func(arr):
    if len(arr) <= 1:
        return 0;

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

    leftBest  = func(left)
    rightBest = func(right)

    crossBest = max(right) - min(left)

    return max(leftBest, rightBest, crossBest)

如果给定列表[12, 9, 18, 3],则我将计算两个元素ij之间的最大差,以使j > ij处的元素减去i处的元素为最大差异。

在这种情况下,我们有j = 2, i = 1,代表18 - 99的最大差异。

我当前的算法返回9,但我希望它返回指标(1, 2)。如何修改这种分而治之的方法来做到这一点?

python algorithm list divide-and-conquer
2个回答
1
投票

而不是返回最大差,而是同时返回索引和最大差。因为您将切片列表传递给递归调用,所以必须调整从递归rightBest调用返回的索引(leftBest调用始终以从“当前” 0到中点的列表开始)。

min()max()一起使用,可以改变最大拾取方式。要选择列表中最大值的索引,请使用range()生成索引,然后使用arr.__getitem__将这些索引映射回列表:

def func(arr):    
    if len(arr) <= 1:
        return 0, 0, 0

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

    leftBest  = func(left)
    ri, rj, rm = func(right)
    rightBest = (ri + mid, rj + mid, rm)

    key = arr.__getitem__
    ci = min(range(0, mid), key=key)
    cj = max(range(mid, len(arr)), key=key)
    crossBest = (ci, cj, arr[cj] - arr[ci])

    return max(leftBest, rightBest, crossBest, key=lambda ijm: ijm[2])

这将返回2个索引以及不同之处:

>>> func([12, 9, 18, 3])
(1, 2, 9)

您必须对结果进行切片以仅获得ij值:

>>> func([12, 9, 18, 3])[:2]
(1, 2)

我什至都不会切片arr列表,因为实际上不需要在此处创建副本。只需将startstop索引传递给递归函数即可替换0len(arr)。我还将使用嵌套函数来进行递归工作。外部函数只能用于提取(i, j)对:

def best_difference_indices(arr):
    arr_get = arr.__getitem__
    max_get = lambda ijm: ijm[2]

    def _func(start, stop):
        if stop - start <= 1:
            return start, start, 0

        mid = (stop - start) // 2 + start
        left_best = _func(start, mid)
        right_best = _func(mid, stop)

        ci = min(range(start, mid), key=arr_get)
        cj = max(range(mid, stop), key=arr_get)
        cross_best = (ci, cj, arr[cj] - arr[ci])

        return max(left_best, right_best, cross_best, key=max_get)

    i, j, _ = _func(0, len(arr))
    return i, j

无需切片,可以更快地完成;输入1000个元素,第二个版本花费<3ms来找到2个索引,而带有切片的版本花费〜3.6 ms;增加20%。


-1
投票

尝试一下:

In [1] arr = [12, 9, 18, 3]

In [2]: diff = 0                                                                                                                                    

In [3]: for i in range(len(arr)): 
    ...:     for j in range(i): 
    ...:         tmp = arr[i] - arr[j] 
    ...:         if tmp > diff: 
    ...:             diff = tmp 
    ...:             result = j, i 
    ...:              
    ...:          
    ...:                                                                                                                                             

In [4]: result                                                                                                                                      
Out[4]: (1, 2)
© www.soinside.com 2019 - 2024. All rights reserved.