Рубрики

Найти пиковый элемент

Дан массив целых чисел. Найдите в нем пиковый элемент. Элемент массива является пиковым, если он НЕ меньше своих соседей. Для угловых элементов нам нужно рассмотреть только одного соседа. Например, для входного массива {5, 10, 20, 15} 20 является единственным пиковым элементом. Для входного массива {10, 20, 15, 2, 23, 90, 67} есть два пиковых элемента: 20 и 90. Обратите внимание, что нам нужно вернуть любой один пиковый элемент.

Следующие угловые случаи дают лучшее представление о проблеме.
1) Если входной массив отсортирован в строго возрастающем порядке, последний элемент всегда является пиковым элементом. Например, 50 является пиковым элементом в {10, 20, 30, 40, 50}.
2) Если входной массив отсортирован в строго убывающем порядке, первый элемент всегда является пиковым элементом. 100 является пиковым элементом в {100, 80, 60, 50, 20}.
3) Если все элементы входного массива одинаковы, каждый элемент является пиковым элементом.

Из приведенных выше примеров ясно, что во входном массиве всегда есть пиковый элемент.

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

Можем ли мы найти пиковый элемент с наихудшей временной сложностью лучше, чем O (n)?
Мы можем использовать Divide and Conquer, чтобы найти пик за время O (Logn). Идея основана на бинарном поиске, мы сравниваем средний элемент с его соседями. Если средний элемент не меньше, чем любой из его соседей, то мы его возвращаем. Если средний элемент меньше, чем его левый сосед, то в левой половине всегда есть пик (почему? Возьмите несколько примеров). Если средний элемент меньше, чем его правый сосед, то в правой половине всегда есть пик (по той же причине, что и левая половина). Ниже приведены C и Java реализации этого подхода.

C ++

// Программа на C ++ для поиска пикового элемента
// используя разделяй и властвуй
#include <bits/stdc++.h>

using namespace std; 

  
// Функция на основе бинарного поиска
// который возвращает индекс элемента вершины

int findPeakUtil(int arr[], int low, 

                 int high, int n) 

    // Найти индекс среднего элемента

    int mid = low + (high - low)/2; / * (низкий + высокий) / 2 * /

  

    // Сравнить средний элемент с его

    // соседи (если соседи существуют)

    if ((mid == 0 || arr[mid - 1] <= arr[mid]) && 

        (mid == n - 1 || arr[mid + 1] <= arr[mid])) 

        return mid; 

  

    // Если средний элемент не пик и его

    // левый сосед больше, чем он,

    // тогда левая половина должна иметь пиковый элемент

    else if (mid > 0 && arr[mid - 1] > arr[mid]) 

        return findPeakUtil(arr, low, (mid - 1), n); 

  

    // Если средний элемент не пик и его

    // правый сосед больше, чем он,

    // тогда правая половина должна иметь пиковый элемент

    else return findPeakUtil(arr, (mid + 1), high, n); 

  
// Обертка над рекурсивной функцией findPeakUtil ()

int findPeak(int arr[], int n) 

    return findPeakUtil(arr, 0, n - 1, n); 

  
// Код драйвера

int main() 

    int arr[] = {1, 3, 20, 4, 1, 0}; 

    int n = sizeof(arr) / sizeof(arr[0]); 

    cout << "Index of a peak point is " 

         << findPeak(arr, n); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// Программа AC для поиска элемента пикового элемента, использующего разделяй и властвуй
#include <stdio.h>

  
// Функция на основе бинарного поиска, которая возвращает индекс элемента пика

int findPeakUtil(int arr[], int low, int high, int n)

{

    // Найти индекс среднего элемента

    int mid = low + (high - low)/2;  / * (низкий + высокий) / 2 * /

  

    // Сравнить средний элемент с его соседями (если соседи существуют)

    if ((mid == 0 || arr[mid-1] <= arr[mid]) &&

            (mid == n-1 || arr[mid+1] <= arr[mid]))

        return mid;

  

    // Если средний элемент не пик, а его левый сосед больше

    // чем это, то левая половина должна иметь пиковый элемент

    else if (mid > 0 && arr[mid-1] > arr[mid])

        return findPeakUtil(arr, low, (mid -1), n);

  

    // Если средний элемент не пик и его правый сосед больше

    // чем тогда правая половина должна иметь пиковый элемент

    else return findPeakUtil(arr, (mid + 1), high, n);

}

  
// Обертка над рекурсивной функцией findPeakUtil ()

int findPeak(int arr[], int n)

{

    return findPeakUtil(arr, 0, n-1, n);

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    int arr[] = {1, 3, 20, 4, 1, 0};

    int n = sizeof(arr)/sizeof(arr[0]);

    printf("Index of a peak point is %d", findPeak(arr, n));

    return 0;

}

Джава

// Java-программа для поиска элемента пикового элемента, использующего разделяй и властвуй

import java.util.*;

import java.lang.*;

import java.io.*;

  

class PeakElement

{

    // Функция на основе бинарного поиска, которая возвращает индекс пика

    // элемент

    static int findPeakUtil(int arr[], int low, int high, int n)

    {

        // Найти индекс среднего элемента

        int mid = low + (high - low)/2/ * (низкий + высокий) / 2 * /

  

        // Сравнить средний элемент с соседями (если соседи

        // существует)

        if ((mid == 0 || arr[mid-1] <= arr[mid]) && (mid == n-1 ||

             arr[mid+1] <= arr[mid]))

            return mid;

  

        // Если средний элемент не пик, а его левый сосед

        // чем больше, то левая половина должна иметь пиковый элемент

        else if (mid > 0 && arr[mid-1] > arr[mid])

            return findPeakUtil(arr, low, (mid -1), n);

  

        // Если средний элемент не вершина и его правый сосед

        // больше, чем правая половина должна иметь пик

        // элемент

        else return findPeakUtil(arr, (mid + 1), high, n);

    }

  

    // Обертка над рекурсивной функцией findPeakUtil ()

    static int findPeak(int arr[], int n)

    {

        return findPeakUtil(arr, 0, n-1, n);

    }

  

    // Метод драйвера

    public static void main (String[] args)

    {

        int arr[] = {1, 3, 20, 4, 1, 0};

        int n = arr.length;

        System.out.println("Index of a peak point is " +

                            findPeak(arr, n));

    }

}

python3

# Программа Python 3 для поиска вершины
# элемент element используя разделяй и властвуй

  
# Функция бинарного поиска
# возвращает индекс пикового элемента

def findPeakUtil(arr, low, high, n):

      

     # Найти индекс среднего элемента

     # (низкий + высокий) / 2

     mid = low + (high - low)/2 

     mid = int(mid)

      

    # Сравните средний элемент с его

    # соседи (если соседи существуют)

    if ((mid == 0 or arr[mid - 1] <= arr[mid]) and 

       (mid == n - 1 or arr[mid + 1] <= arr[mid])):

        return mid

  

  

    # Если средний элемент не пик и

    # его левый сосед больше

    # чем то, то левая половина должна

    # есть пик элемент

    elif (mid > 0 and arr[mid - 1] > arr[mid]):

        return findPeakUtil(arr, low, (mid - 1), n)

  

    # Если средний элемент не пик и

    # его правый сосед больше

    # чем то, то правая половина должна

    # есть пик элемент

    else:

        return findPeakUtil(arr, (mid + 1), high, n)

  

  
# Обертка над рекурсивной
# function findPeakUtil ()

def findPeak(arr, n):

  

    return findPeakUtil(arr, 0, n - 1, n)

  

  
# Код драйвера

arr = [1, 3, 20, 4, 1, 0]

n = len(arr)

print("Index of a peak point is", findPeak(arr, n))

      
# Этот код предоставлен
# Смита Динеш Семвал

C #

// AC # программа для поиска
// элемент пикового элемента
// используя разделяй и властвуй

using System;

  

class GFG

{

      

    // Бинарный поиск на основе

    // функция, которая возвращает

    // индекс элемента пика

    static int findPeakUtil(int []arr, int low,

                            int high, int n)

    {

        // Найти индекс

        // средний элемент

        int mid = low + (high - low) / 2; 

  

        // Сравнить средний элемент с

        // его соседи (если соседи

        // существует)

        if ((mid == 0 || 

             arr[mid - 1] <= arr[mid]) && 

            (mid == n - 1 || 

             arr[mid + 1] <= arr[mid]))

            return mid;

  

        // Если среднего элемента нет

        // пик и его левый сосед

        // тогда больше

        // левая половина должна иметь

        // пиковый элемент

        else if (mid > 0 && 

                 arr[mid - 1] > arr[mid])

            return findPeakUtil(arr, low, 

                               (mid - 1), n);

  

        // Если среднего элемента нет

        // вершина и ее правый сосед

        // тогда больше

        // правая половина должна иметь пик

        // элемент

        else return findPeakUtil(arr, (mid + 1), 

                                 high, n);

    }

  

    // Обёртка над рекурсивом

    // функция findPeakUtil ()

    static int findPeak(int []arr, 

                        int n)

    {

        return findPeakUtil(arr, 0, 

                            n - 1, n);

    }

  

    // Код драйвера

    static public void Main ()

    {

        int []arr = {1, 3, 20,

                     4, 1, 0};

        int n = arr.Length;

        Console.WriteLine("Index of a peak " +

                                 "point is " +

                            findPeak(arr, n));

    }

}

  
// Этот код предоставлен ajit

PHP

<?php
// PHP программа для поиска
// элемент пика с использованием
// разделяй и властвуй

  
// Функция на основе бинарного поиска
// который возвращает индекс пика
// элемент

function findPeakUtil($arr, $low

                      $high, $n)

{

    // Найти индекс среднего элемента

    $mid = $low + ($high - $low) / 2; // (низкий + высокий) / 2

  

    // Сравнить средний элемент с

    // его соседи (если соседи существуют)

    if (($mid == 0 || 

         $arr[$mid - 1] <= $arr[$mid]) &&

        ($mid == $n - 1 || 

         $arr[$mid + 1] <= $arr[$mid]))

        return $mid;

  

    // Если средний элемент не пик

    // и его левый сосед больше

    // чем это, то левая половина должна

    // есть пиковый элемент

    else if ($mid > 0 && 

             $arr[$mid - 1] > $arr[$mid])

        return findPeakUtil($arr, $low

                           ($mid - 1), $n);

  

    // Если средний элемент не пик

    // и его правый сосед

    // больше, чем право

    // половина должна иметь пиковый элемент

    else return(findPeakUtil($arr, ($mid + 1), 

                             $high, $n));

}

  
// Обёртка над рекурсивом
// функция findPeakUtil ()

function findPeak($arr, $n)

{

    return floor(findPeakUtil($arr, 0, 

                              $n - 1, $n));

}

  
// Код драйвера

$arr = array(1, 3, 20, 4, 1, 0);

$n = sizeof($arr);

echo "Index of a peak point is "

              findPeak($arr, $n);

  
// Этот код предоставлен ajit
?>


Выход :

Index of a peak point is 2

Сложность времени: O (Logn), где n — количество элементов во входном массиве.

Упражнение:
Рассмотрим следующее модифицированное определение пикового элемента. Элемент массива является пиковым, если он больше, чем его соседи. Обратите внимание, что массив может не содержать пиковый элемент с этим измененным определением.

Ссылки:
http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
http://www.youtube.com/watch?v=HtSuA80QTyo

Спросил в: Amazon

Связанная проблема:
Найти локальные минимумы в массиве

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти пиковый элемент

0.00 (0%) 0 votes