Dizidən Zirvə Elementini tapın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Bloomberg ByteDance DE Şou Facebook google microsoft Quora Über Walmart Laboratoriyaları
Geyim İkili axtarış Duolingo AxtarışBaxılıb 610

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

"Bir Dövrdən Pik Elementi tap" problemində bir giriş verdik array tam ədədi. Bir zirvə elementi tapın. Bir sıra, element hər iki qonşudan daha böyükdürsə, bir element zirvə elementidir. Künc elementləri üçün mövcud qonşu hesab edə bilərik.

Giriş Formatı

Bir tam ədədi olan ilk və yalnız bir sətir.

N boşluqla ayrılmış tam ədədi olan ikinci sətir.

Çıxış formatı

Dizinin zirvə elementini ifadə edən bir tam ədədi ehtiva edən ilk və yalnız bir sətir.

Məhdudiyyətlər

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

misal

6
7 11 17 33 21 19
33

Explanation: 33-ün qonşuları 21 və 17-dir. 33 21-dən və 17-dən böyükdür, buna görə də 33 zirvə elementidir.

7
1 2 3 4 5 6 7
7

Explanation: 7-nin qonşusu yalnız 5-dir (künc elementi). 7 5-dən böyükdür Buna görə 7 zirvə elementidir.

5
45 35 25 15 5
45

Explanation: 45-in qonşusu yalnız 35-dir (künc elementi). 45> 35, Buna görə 33 zirvə elementidir.

8
5 19 24 14 8 4 26 12
24

Explanation: Burada 24-ün qonşuları 19 və 14, 26-nın qonşuları 4 və 12-dir. 24 19 və 14-dən, 26-sı 4 və 12-dən böyükdür. Buna görə 24 və 26-nın hər ikisi pik elementləridir. Cavabımız olaraq 24 yazdırırıq. 26 nı da çap edə bilərik ki, bu da etibarlı bir cavabdır.

Bir massivdən zirvə elementini tapmaq üçün alqoritm

Hər iki qonşusundan daha böyük olan elementi tapmaq üçün xətti bir axtarış edə bilərik. Ancaq O (n) vaxt tələb olunur. Beləliklə, O (logn) vaxtında zirvəni tapmaq üçün böl və fəth metodundan istifadə edirik. Burada dəyişdirilmiş ikili axtarış aparırıq -

a. Orta element hər iki qonşudan daha böyükdürsə, orta elementi qaytarırıq.
b. Orta element sol qonşudan kiçikdirsə, zirvə elementi massivin sol yarısında olmalıdır.
c. Orta element sağ qonşudan daha kiçikdirsə, pik element massivin sağ yarısında olmalıdır.

Həyata keçirilməsi

Bir Cərgədən Pik Elementini Tapmaq üçün C ++ Proqramı

#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;
}

Dizidən Zirvə Elementini Tapmaq üçün Java Proqramı

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

Bir Dizidən Pik Elementi Tapmaq üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (logN) hara N verilmiş massivin ölçüsüdür. Burada bizi logN vaxt mürəkkəbliyinə aparan ikili axtarış konsepsiyasından istifadə edirik.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

Crack Sistemi Dizayn Müsahibələri
Translate »