배열에서 피크 요소 찾기

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

“배열에서 피크 요소 찾기”문제에서 우리는 정렬 정수 피크 요소를 찾으십시오. 배열에서 요소가 두 인접 요소보다 크면 요소는 피크 요소입니다. 모서리 요소의 경우 현재 유일한 이웃을 고려할 수 있습니다.

입력 형식

정수 N을 포함하는 첫 번째이자 유일한 행입니다.

N 개의 공백으로 구분 된 정수를 포함하는 두 번째 줄.

출력 형식

배열의 피크 요소를 나타내는 정수를 포함하는 첫 번째 및 유일한 행입니다.

제약

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

예

6
7 11 17 33 21 19

33

설명 : 33의 이웃은 21과 17입니다. 33은 21과 17보다 크므로 33은 피크 요소입니다.

7
1 2 3 4 5 6 7

7

설명 : 7의 이웃은 5 (코너 요소)뿐입니다. 7은 5보다 크므로 7은 피크 요소입니다.

5
45 35 25 15 5

45

설명 : 45의 이웃은 35 (코너 요소)입니다. 45> 35, 따라서 33은 피크 요소입니다.

8
5 19 24 14 8 4 26 12

24

설명 : 여기서 24의 이웃은 19와 14이고 26의 이웃은 4와 12입니다. 24는 19와 14보다 크고 26은 4와 12보다 큽니다. 따라서 24와 26은 모두 피크 요소입니다. 답으로 24를 인쇄합니다. 또한 유효한 답인 26을 인쇄 할 수도 있습니다.

배열에서 피크 요소를 찾는 알고리즘

선형 검색을 수행하여 두 이웃보다 큰 요소를 찾을 수 있습니다. 그러나 O (n) 시간이 걸립니다. 그래서 우리는 나누기 및 정복 방법을 사용하여 O (logn) 시간의 피크를 찾습니다. 여기에서 수정 된 이진 검색을 수행합니다.

a. 중간 요소가 두 인접 요소보다 크면 중간 요소를 반환합니다.
b. 중간 요소가 왼쪽 이웃보다 작은 경우 피크 요소는 배열의 왼쪽 절반에 있어야합니다.
c. 가운데 요소가 오른쪽 이웃보다 작은 경우 피크 요소는 배열의 오른쪽 절반에 있어야합니다.

실시

배열에서 피크 요소를 찾는 C ++ 프로그램

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

어레이에서 피크 요소를 찾는 Java 프로그램

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

배열에서 피크 요소를 찾기위한 복잡성 분석

시간 복잡성

O (logN) 어디에 N 주어진 배열의 크기입니다. 여기서 우리는 logN 시간 복잡성을 유발하는 이진 검색 개념을 사용합니다.

공간 복잡성