피크 요소 찾기

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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)

참조

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

삽입 정렬