查找数组的局部最大值及其位置的问题 Python

Question

所以基本上我正在努力完成这项任务：https://www.codewars.com/kata/5279f6fe5ab7f447890006a7

问题是：为什么我的函数将位置11计算为这个特定数组的局部最大值？这是我的代码：

def main():
arr = [1,2,5,4,3,2,3,6,4,1,2,3,3,4,5,3,2,1,2,3,5,5,4,3]
maxes = []
positions = []
dic = {"pos":positions, "peaks":maxes}
for i in range(1,len(arr)-1):
try:
if arr[i] > arr[i+1] and arr[i] > arr[i-1]:
maxes.append(arr[i])
positions.append(i)
elif arr[i] > arr[i-1] and arr[i] == arr[i+1]:
for a in range(i+1,len(arr)):
if arr[a] > arr[a+1]:
maxes.append(arr[i])
positions.append(i)
break
except IndexError:
pass
print(dic)
main()

我的输出：

{'pos': [2, 7, 11, 14, 20], 'peaks': [5, 6, 3, 5, 5]}

正确输出：

{'pos': [2, 7, 14, 20], 'peaks': [5, 6, 5, 5]}

Answer 1

当您看到类似"2，3，3，4,5,3"您保存位置并进一步运行，试图找出：1(最后值较小(然后这是峰值，保存的值派上了用场(，2(值较大(不是峰值，平台，保存的数值没有用处(。

在第二种情况下的特殊情况下：elif arr[i] > arr[i-1] and arr[i] == arr[i+1]:您从第二个3开始迭代，并且仅在arr[a] > arr[a+1]时停止。此时，您附加旧的i值(表示前3个(：

maxes.append(arr[i]); positions.append(i)

也就是说，你没有考虑到这个值可能会更大，你需要中断。

该功能的工作示例如下：

def main():
arr = [1,2,5,4,3,2,3,6,4,1,2,3,3,4,5,3,2,1,2,3,5,5,4,3]
dic = {'pos' : [], 'peaks' : []}
i, n = 1, len(arr)
while i < n - 1:
if arr[i-1] < arr[i] > arr[i+1]:
dic['peaks'].append(arr[i])
dic['pos'].append(i)
i += 1
else:
if arr[i-1] < arr[i] and arr[i] == arr[i+1]:
mem = i
while i < n -1 and arr[i] == arr[i+1]:
i += 1

if i == n - 1:
return dic

if arr[i] > arr[i+1]:
dic['peaks'].append(arr[mem])
dic['pos'].append(mem)
else:
i += 1  
else:
i += 1
return dic
print(main())

Answer 2

当您找到以下相等的值并继续搜索较小的值时，如果您找到较大的值，也应该中断循环。如果等号后面跟一个更大的值，这就不是峰值。

一个小的添加就足以使代码正常工作。

def main():
arr = [1,2,5,4,3,2,3,6,4,1,2,3,3,4,5,3,2,1,2,3,5,5,4,3]
maxes = []
positions = []
dic = {"pos":positions, "peaks":maxes}
for i in range(1,len(arr)-1):
try:
if arr[i] > arr[i+1] and arr[i] > arr[i-1]:
maxes.append(arr[i])
positions.append(i)
elif arr[i] > arr[i-1] and arr[i] == arr[i+1]:
for a in range(i+1,len(arr)):
if arr[a] > arr[a+1]:
maxes.append(arr[i])
positions.append(i)
break
# also break if a greater value is found
elif arr[a] < arr[a+1]:
break
except IndexError:
pass
print(dic)
main()

一种更简单的方法可能是只迭代一次，并在每次发现增长时记下位置。然后保存该位置及其值，当您发现之后有所减少时。

def pick_peaks(arr):
dic = {"pos":[], "peaks":[]}
possible_peak = None
for i in range(1,len(arr)):
if arr[i] > arr[i-1]:
# Value is going up. Remember position
possible_peak = i
elif arr[i] < arr[i-1] and possible_peak != None:
# It was indeed a peak. Save it.
dic["pos"].append(possible_peak)
dic["peaks"].append(arr[possible_peak])
# reset memory until new increase is found
possible_peak = None
return dic
input_arr = [1,2,5,4,3,2,3,6,4,1,2,3,3,4,5,3,2,1,2,3,5,5,4,3]
print(pick_peaks(input_arr))