Znajdź element szczytowy z tablicy

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

W zadaniu „Znajdź element szczytowy z tablicy” podaliśmy dane wejściowe szyk liczb całkowitych. Znajdź szczytowy element. W tablicy element jest elementem szczytowym, jeśli element jest większy od obu sąsiadów. W przypadku elementów narożnych możemy wziąć pod uwagę jedynego obecnego sąsiada.

Format wejściowy

Pierwszy i jedyny wiersz zawierający liczbę całkowitą N.

Drugi wiersz zawierający N liczb całkowitych oddzielonych spacjami.

Format wyjściowy

Pierwszy i jedyny wiersz zawierający liczbę całkowitą, która oznacza element szczytowy tablicy.

ograniczenia

• 1 <= N <= 10 ^ 5
• -10 ^ 9 <= N <= 10 ^ 9

Przykład

6
7 11 17 33 21 19

33

Wyjaśnienie: Sąsiedzi z 33 to 21 i 17. 33 jest większe niż 21 i 17, dlatego 33 to element szczytowy.

7
1 2 3 4 5 6 7

7

Wyjaśnienie: Sąsiadem 7 jest tylko 5 (element narożny). 7 jest większe niż 5 Dlatego 7 jest elementem szczytowym.

5
45 35 25 15 5

45

Wyjaśnienie: Sąsiad 45 ma tylko 35 (element narożny). 45> 35, więc 33 to element szczytowy.

8
5 19 24 14 8 4 26 12

24

Wyjaśnienie: Tutaj sąsiedzi z liczby 24 mają 19 i 14, a sąsiedzi z liczby 26 mają 4 i 12. 24 jest większe niż 19 i 14, 26 jest większe niż 4 i 12. Zatem, 24 i 26 to oba elementy szczytowe. Jako odpowiedź drukujemy 24. Możemy również wydrukować 26, co jest również prawidłową odpowiedzią.

Algorytm znajdowania elementu szczytowego z tablicy

Możemy przeprowadzić wyszukiwanie liniowe, aby znaleźć element, który jest większy od obu jego sąsiadów. Ale zajmuje to O (n) czasu. Tak więc używamy metody dziel i zwyciężaj, aby znaleźć szczyt w czasie O (logn). Tutaj wykonujemy zmodyfikowane wyszukiwanie binarne-

a. Jeśli środkowy element jest większy niż obaj sąsiedzi, zwracamy środkowy element.
b. Jeśli środkowy element jest mniejszy niż lewy sąsiad, element szczytowy musi znajdować się w lewej połowie tablicy.
c. Jeśli środkowy element jest mniejszy niż prawy sąsiad, element szczytowy musi znajdować się w prawej połowie tablicy.

Realizacja

Program w C ++ do znajdowania elementu szczytowego z tablicy

#include <bits/stdc++.h>
using namespace std;

//Function to find peak element
//Modified Binary search
int FindPeak(int array[], int low, int high, int n)
{
    int mid = low + (high - low)/2;
    //return mid 
    //If mid is greater than neighbours or mid = 0
    //If neighbours exist
    if((mid == 0 || array[mid-1] <= array[mid]) && (mid == n-1 || array[mid+1] <= array[mid]))
    {
        return mid;
    }
    //If mid is not peak and its right neighbour is greater.
    //then search in right half 
    else if(mid > 0 && array[mid-1] < array[mid])
    {
        return FindPeak(array, (mid + 1), high, n);
    }
    //If mid is not peak and its left neighbour is greater.
    //then search in left half
    else
    {
        return FindPeak(array, low, (mid -1), n);
    }
}

int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int index = FindPeak(a, 0, n-1, n);
    cout<<a[index]<<endl;
    return 0;
}

Program Java do znajdowania elementu szczytowego z tablicy

import java.util.Scanner;
class sum
{
    //Function to find peak element
    //Modified Binary search
    public static int FindPeak(int array[], int low, int high, int n)
    {
        int mid = low + (high - low)/2;
        //return mid 
        //If mid is greater than neighbours or mid = 0
        //If neighbours exist
        if((mid == 0 || array[mid-1] <= array[mid]) && (mid == n-1 || array[mid+1] <= array[mid]))
        {
            return mid;
        }
        //If mid is not peak and its right neighbour is greater.
        //then search in right half 
        else if(mid > 0 && array[mid-1] < array[mid])
        {
            return FindPeak(array, (mid + 1), high, n);
        }
        //If mid is not peak and its left neighbour is greater.
        //then search in left half
        else
        {
            return FindPeak(array, low, (mid -1), n);
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int index = FindPeak(a, 0, n-1, n);
        System.out.println(a[index]);
}

8 
5 19 24 14 8 4 26 12

24

Analiza złożoności w celu znalezienia elementu szczytowego z tablicy

Złożoność czasowa

O (logN) gdzie N jest rozmiarem podanej tablicy. Tutaj używamy pojęcia wyszukiwania binarnego, które prowadzi nas do złożoności czasu logowania.

Złożoność przestrzeni