회전 정렬 된 배열에서 최소값 찾기

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Microsoft 모건 스탠리 (Morgan Stanley) 삼성 스냅 딜 타임즈 인터넷
배열 이진 검색 분열과 정복 수색조회수 104

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

문제 정책

"회전 된 정렬 된 배열에서 최소값 찾기"는 어떤 인덱스에서 회전 된 크기 n의 정렬 된 배열이 제공된다는 것을 나타냅니다. 최소 요소 찾기 정렬.

회전 정렬 된 배열에서 최소값 찾기

a[ ] = {5, 1, 2, 3, 4}
1

설명 : 배열을 정렬 된 순서로 정렬하면 [1, 2, 3, 4, 5]가됩니다. 따라서이 모든 것 중 가장 작은 숫자는 1입니다. 그래서 출력이 1입니다.

a[ ] = {5, 2, 3, 4}
2

선형 검색

암호알고리즘

1. Initialize a sorted rotated array a[ ] of size n.
2. Create a function to find the minimum in a rotated sorted array which accepts an integer variable as it's a parameter.
3. Initialize an integer variable min as the first element in the given array.
4. Traverse through the given array and check if the element at current index in array a[ ] is less than variable min, update min as current element.
5. Return the integer variable min.

선형 검색을 사용하거나 단순히 입력 배열을 한 번 순회하고 단일 순회에서 가장 작은 요소를 찾을 수 있습니다. 배열의 모든 요소를 ​​간단히 반복하고 최소값보다 작은 숫자를 찾으면 답변을 업데이트합니다.

암호

회전 정렬 된 배열에서 최소값을 찾는 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

int findMin(int a[], int n){
    int min = a[0];
    for(int i=1; i<n; i++){
        if(a[i]<min){
            min = a[i];
        }
    }
    return min;
}

int main() {
  int a[] = {5, 2, 3, 4};
  int n = sizeof(a)/sizeof(a[0]);
  cout<<findMin(a, n);
  return 0;
}
2

회전 정렬 된 배열에서 최소값을 찾는 Java 프로그램

class MinSearch{
    
    static int findMin(int a[], int n){
        int min = a[0];
        for(int i=1; i<n; i++){
            if(a[i]<min){
                min = a[i];
            }
        }
        return min;
    }
    
  public static void main (String[] args){
    int a[] = {5, 2, 3, 4};
      int n = a.length;
      System.out.println(findMin(a, n));
  }
}


2

복잡성 분석

시간 복잡성

의 위에),  배열의 모든 요소를 ​​순회했기 때문에 선형 시간 복잡성을 얻을 수있었습니다.

공간 복잡성

O (1), 알고리즘 자체는 일정한 공간을 차지하지만 프로그램은 입력 배열을 저장하기 때문에 전체적으로 선형 공간을 차지합니다.

이진 검색

암호알고리즘

1. Initialize a sorted rotated array a[ ] of size n.
2. Create a function to find the minimum in a rotated sorted array which accepts an integer variable as it's a parameter.
3. Initialise the three variables beg = 0, end = n-1 and mid = beg+(end-beg)/2.
4. Check if the variable end is less than the variable beg, return a[0].
5. If the variable end is equal to the variable beg, return a[beg].
6. If the variable mid is less than the variable end and a[mid+1] is less than a[mid], return a[mid+1].
7. If mid is greater than beg and a[mid] is less than a[mid+1], return a[mid].
8. If a[end] is greater than a[mid], make a recursive call to function with parameters a, beg, mid-1.
9. Return the recursive call to function itself with the parameters a, mid+1, and end.

더 효율적인 접근 방식은 입력 배열이 회전 정렬 배열이기 때문에 이진 검색을 사용하는 것입니다. 그것은 배열이 정렬되었지만 단일 지점에서 회전되었습니다. 이진 검색에는 로그 시간 복잡성이 필요하기 때문입니다. 위의 솔루션과 비교하여이 솔루션을 사용하는 것이 좋습니다.

이진 검색을 사용하여 회전 정렬 된 배열에서 최소값을 찾는 코드

C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
int findMin(int a[], int beg, int end){  
    if(end < beg) 
        return a[0];  
  
    if(end==beg) 
        return a[beg];  
  
    int mid = beg + (end - beg)/2; 
  
    if(mid<end && a[mid + 1]<a[mid])  
        return a[mid + 1];  
  
    if(mid>beg && a[mid]<a[mid - 1])  
        return a[mid];  
  
    if(a[end]>a[mid])  
    return findMin(a, beg, mid - 1);  
    return findMin(a, mid + 1, end);  
}  
  
int main(){  
    int a[] = {5, 2, 3, 4}; 
    int n = sizeof(a)/sizeof(a[0]);  
    cout<<findMin(a, 0, n-1);  
    return 0;  
}
2

자바 프로그램

class MinSearch{ 
   
    static int findMin(int a[], int beg, int end){ 
        
        if(end < beg) 
            return a[0]; 
            
        if(end==beg) 
            return a[beg];
            
        int mid = beg + (end - beg)/2; 
        
        if(mid<end && a[mid + 1]<a[mid]) 
            return a[mid + 1]; 
        
        if(mid>beg && a[mid]<a[mid - 1]) 
            return a[mid]; 
        
        if(a[end]>a[mid]) 
            return findMin(a, beg, mid - 1); 
        return findMin(a, mid + 1, end); 
    }
        
    public static void main (String[] args){ 
        int a[] = {5, 2, 3, 4}; 
        int n = a.length; 
        System.out.println(findMin(a, 0, n-1)); 
    } 
}
2

복잡성 분석

시간 복잡성

O (로그 N) 여기서 N은 입력 배열의 요소 수입니다. 여기서 우리는 로그 시간 복잡도를 취하는 이진 검색을 사용했습니다. 이 모든 것은 배열이 처음에 정렬 되었기 때문에 가능합니다.

공간 복잡성

O (1), 이 접근법은 또한 일정한 시간이 걸리지 만 입력을 저장하는 데 필요한 공간 때문에 프로그램 전체가 O (N) 공간을 차지합니다.

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