我有一个递归函数,它可以找到任意两个整数之间的最大差,只要第二个索引处的值比第一个索引处的值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]
,则我将计算两个元素i
,j
之间的最大差,以使j > i
和j
处的元素减去i
处的元素为最大差异。
在这种情况下,我们有j = 2, i = 1
,代表18 - 9
是9
的最大差异。
我当前的算法返回9
,但我希望它返回指标(1, 2)
。如何修改这种分而治之的方法来做到这一点?
而不是返回最大差,而是同时返回索引和最大差。因为您将切片列表传递给递归调用,所以必须调整从递归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)
您必须对结果进行切片以仅获得i
和j
值:
>>> func([12, 9, 18, 3])[:2]
(1, 2)
我什至都不会切片arr
列表,因为实际上不需要在此处创建副本。只需将start
和stop
索引传递给递归函数即可替换0
和len(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%。
尝试一下:
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)