Найдите вершины массива

Python опрос

Три месяца назад мне задали интересный вопрос по алгоритму, долго думал, прежде чем придумал, теперь пишу блог, чтобы его записать.

Учитывая очень длинный массив arr, известна длина массива и длина >= 3, известно, что первый элемент массива не больше второго элемента, а последний элемент массива не больше предпоследнего элемент. Затем найдите этот массивлюбойИндексы массива пиков. PS: Элементы, которые не меньше предыдущего элемента и не меньше последнего элемента, называются гребнями.

arr[1] >= arr[0], то просто нужноarr[1] >= arr[2]1 — пик.

еслиarr[1] < arr[2], то просто нужноarr[2] >= arr[3]2 - пик.

...

На самом деле это может быть абстрагировано в задачу динамического программирования. Но это не обязательно и, очевидно, все равно нужно пройти после абстракции...

Подождите... что, если массив с удаленными первым и последним элементами является последовательно увеличивающимся массивом, и в этом случае нам нужно очистить весь массив, заплатив сложность O (N). Думаете, это немного похоже на серию махинаций, каждый раз, когда указатель перемещается к элементу, удовлетворяющему первой части условий гребня волны (не меньшему, чем предыдущий элемент), мы радостно ожидаем, что он удовлетворяет условиям второй половины, но иногда это не сбывается.

Вы когда-нибудь задумывались о бинарном поиске?

Действительно, это очень похоже на проблему, которую может решить бинарный поиск. ноМассивы не говорят, что они упорядочены.. Поэтому основные условия бинарного поиска вообще не выполняются.

С мертвой лошадью нужно обращаться как с живой лошадью-врачом?

Что ж, тогда попробуем. Берем элемент в самой середине массива, который называемarr[length/2].
Получив его, не должны ли мы безнадежно сравнивать его с его левым и правым элементами? Поскольку это сравнение происходит с массивами, накладные расходы незначительны.
Если он больше, чем левый и правый, то это, очевидно, гребень волны, тогда верните его индекс в это время.length/2Вот и все.
Так что, если он меньше, чем тот, что слева, или меньше, чем тот, что справа, или меньше, чем оба?
Так можно ли найти гребень волны слева или справа, и как определить, что гребень волны должен быть слева или справа?

В это время мы должны заметить две проблемы.

  1. Если он меньше, чем тот, что слева, тоarr[:length/2+1]Этот подмассив также является массивом, отвечающим условиям, заданным вопросом. Если он меньше, чем тот, что справа, тоarr[length/2:]Этот подмассив также является массивом, отвечающим условиям, заданным вопросом.
  2. Обязательно ли найдется гребень, если посмотреть налево или направо? Другими словами, обязательно ли в массиве есть хотя бы один пик, удовлетворяющий заданным условиям?

Если обратить внимание на эти две проблемы, то эта проблема решаема.
Приведите пример кода (чистый почерк...)

def find_peak(arr, length):
    if length < 3:
        return -1

    middle = length / 2
    if length < 5:
        return middle 
    
    if arr[middle] > arr[middle - 1] and arr[middle] > arr[middle + 1]:
        return middle
    if arr[middle] < arr[middle - 1]:
        return find_peak(arr[:middle + 1], middle + 1)
    sub_length = middle + 1
    if length % 2 == 0:
        sub_length = middle
    return find_peak(arr[middle:], sub_length)

Эта реализация кода должна учитывать множество границ, возможно, мой код этого не учел, если есть проблема, добро пожаловать, чтобы сделать кирпич.

Категории