Блог

Главная - Вопросы по программированию - Проблема с поиском локальных максимумов массива и их позиций Python

Проблема с поиском локальных максимумов массива и их позиций Python

#python #arrays

#python #массивы

Вопрос:

Итак, в основном я пытаюсь выполнить это задание: 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]}

Комментарии:

1. Потому что в цикле во втором условии вы выполняете итерацию по a, но добавляете i

Ответ №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())

Ответ №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))

Комментарии:

1. Спасибо! Я знал, что это что-то простое, но просто не мог понять

Метки: