피크 요소 찾기

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance Facebook 구글 Quora 비자,
배열 이진 검색 분열과 정복 수색조회수 72

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

이해합시다 피크 요소 찾기 문제. 오늘 우리는 우리와 함께 정렬 피크 요소가 필요합니다. 이제 피크 요소가 무엇을 의미하는지 궁금 할 것입니다. 피크 요소는 모든 이웃보다 큰 요소입니다.

: [1,2,3,1]의 배열이 주어집니다.

피크 요소: 3

이미지 표현으로 더 잘 이해합시다

피크 요소 찾기
예제 어레이에 대한 피크 요소 표시

위의 이미지는 4 개의 주변 요소가 어떻게 눈에 띄는 지 완벽하게 보여줍니다. 피크 요소. 지금 우리 앞에 놓인 도전은 주어진 문제에 접근하는 방법입니다.

접근 방식 -1

피크 요소 찾기에 대한 무차별 대입

이미지에서 얻을 수있는 표준 관찰은 전체 배열에서 최대 요소 (눈에 띄는 요소)를 반환하는 것입니다.

배열에서 최대 요소를 찾는 과정을 훑어 보겠습니다.

  • 최대 변수를 유지하십시오. 처음에 배열의 0 번째 요소로 값을 넣으십시오.
  • 인덱스를 저장할 변수를 유지하십시오. 여기, j.
  • 전체 어레이를 통해 루프 실행
    • max보다 큰 값을 만날 때마다
      • 변수 최대 업데이트
      • j에 새 인덱스 값을 입력하십시오.
  • 반환 j

피크 요소 찾기를위한 C ++ 코드

class Solution 
{
public:
    int findPeakElement(vector<int>& nums) 
    {
     int max=nums[0];
     int pos=0;
     for(int i=0;i<nums.size();i++)
     {
      if(max<nums[i]) 
      {
          max=nums[i];
          pos=i;
      }
     }
    return pos;    
    }
};
7
1 3 8 2 1 5 3
2

피크 요소 찾기를위한 Java 코드

class Solution 
{
    public int findPeakElement(int[] nums) 
    {
     int max=nums[0];
     int pos=0;
     for(int i=0;i<nums.length;i++)
     {
      if(max<nums[i]) 
      {
          max=nums[i];
          pos=i;
      }
     }
    return pos;
    }
}
5
-10 1 0 10 5
3

시간 복잡성 접근 방식 = O (n)

우리는 모든 것을 더 빠르게 만들 수있는 시대에 살고 있습니다. 그렇다면이 솔루션은 어떻습니까?

위에서부터 가져 와서 O (log n)로 만듭니다.

접근 방식 -2

검색 바이너리 화

이제 선형 수단을 모두 사용 했으므로 log (n) 모든 것의 어머니 인 바이너리 그림을 가져 오겠습니다.

여기서 우리는 무엇을합니까?

  • 두 포인터를 높고 낮게 유지
  • 포인터를 사용하여 중간 점 계산
    • 중간 요소가 인접한 요소보다 클 때마다
      • 배열의 전반부에서 더 클 수있는 요소를 검색하기 시작합니다.
      • 이유는 무엇입니까?
        • 후반은 확실히 우리의 더 큰 규칙을 배반 한 전반에 그들의 정점을 넘겼습니다.
    • 중간 요소가 인접한 요소보다 작을 때마다
      • 배열의 후반부에서 이웃보다 클 수있는 요소를 검색하기 시작합니다.
      • 이유는 무엇입니까?
        • 전반은 확실히 우리의 더 큰 규칙을 배반하여 그들의 정점을 후반에 넘겼습니다.
    • 저점이 고점보다 커질 때까지 계속 반복하십시오.
    • 요소가 낮은 위치에 포함되어있는 그대로 피크 요소 

자바 코드

class Solution 
{
    public int findPeakElement(int[] nums) 
    {
    int low=0;
     int hig=nums.length-1;
     while(hig>low)
     {
         int mid=low+(hig-low)/2;
         if(nums[mid]>nums[mid+1])
             hig=mid;
         else
             low=mid+1;
     }
     return low;    
    }
}
5
10 11 0 10 5
1

C ++ 코드

class Solution 
{
    public:
    int findPeakElement(vector<int>& nums) 
    {
     int low=0;
     int hig=nums.size()-1;
     while(hig>low)
     {
         int mid=low+(hig-low)/2;
         if(nums[mid]>nums[mid+1])
             hig=mid;
         else
             low=mid+1;
     }
     return low;    
    }
};
5
0 1 0 14 5
1

또한 시간 복잡성 위의 접근 방식 = O (log n)

공간 복잡성 = O (1)

참조

배우는 것을 멈추지 말고 가장 흥미로운 분류 기술 중 하나를 따라 잡으십시오.

삽입 정렬

균열 시스템 설계 인터뷰
Translate »