Znajdź element szczytowy z tablicy

Poziom trudności Średni
Często zadawane pytania Amazonka Apple Bloomberg ByteDance DE Shaw Facebook Google Microsoft Quora Uber Laboratoria Walmart
Szyk Wyszukiwanie binarne Duolingo Badawczyodwiedzajacy 610

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

O (1) ponieważ nie używamy tutaj żadnej dodatkowej spacji.

Wywiady dotyczące projektowania systemu pękania
Translate »