정렬 된 배열에서 가장 작은 누락 된 수 찾기

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 자본 하나 시스코 이베이 Facebook 골드만 삭스 구글 IBM JP 모건 Microsoft 엔비디아 신탁 페이팔 ServiceNow Yandex 주차
Arista Networks 배열 수학조회수 590

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

문제 정책

"정렬 된 배열에서 가장 작은 누락 된 수 찾기"문제에서 정수 배열을 제공했습니다. 정렬 된 N 크기에서 가장 작은 누락 된 숫자 찾기 정렬 0 ~ M-1 범위의 고유 요소를 가지며, 여기서 M> N.

입력

[0, 1, 2, 3, 4, 6, 7, 8, 9]

산출

5

입력

[0,1,2,4,5,6,7,8]

산출

3

입력

[0,1,2,3,4,5,6,8,9]

산출

7

입력

[0,1,2,3,4,5,7,8,9]

산출

6

정렬 된 배열에서 가장 작은 누락 된 수 찾기에 대한 접근 방식 1

여기서 우리는 단순히 배열 요소가 더 크면 해당 숫자 (i)가 누락 된 경우 인덱스와 배열 요소를 비교합니다. 이제 C ++ 언어를 사용한 구현으로 이동합니다.

실시

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,m;
  cin>>n>>m;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  for(int i=0;i<n;i++)
  {
      if(a[i]>i)
      {
        cout<<i<<endl;
        return 0;
      }
  }
  cout<<n<<endl;
  return 0;
}

자바 프로그램

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int temp=0;
        for(int i=0;i<n;i++)
        {
            if(arr[i]>i)
            {
              System.out.println(i);
              temp=1;
              i=n;
            }
        }
        if(temp==0)
        System.out.println(n);
    }
}
9 11
0 1 2 3 4 5 8 9 10
6

정렬 된 배열에서 가장 작은 누락 된 수 찾기를위한 복잡성 분석

시간 복잡성 – O (N) 여기서 n은 배열의 크기를 나타냅니다. 여기서 우리는 배열을 순회하고 답을 찾으면 인쇄하고 반환합니다.

공간 복잡성 – O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.

정렬 된 배열에서 가장 작은 누락 된 수 찾기에 대한 접근 방식 2

여기에서는 배열이 이미 정렬되어 있기 때문에 이진 검색의 개념을 사용합니다. 여기서 우리는 0에서 M까지 범위에서 i의 각 값을 검색합니다. 요소가 없으면 해당 요소를 인쇄하고 반환합니다.

암호알고리즘

  1. 0에서 M-1까지 루프를 실행하고
  2. 범위의 각 요소를 이진 검색하고 숫자가 있는지 여부를 확인합니다.
  3. [0,1,2,4,5,6,7,8]은 주어진 배열이므로 여기서 범위는 0에서 8까지입니다. 배열에서 0에서 8까지의 모든 숫자를 이진 검색합니다.
  4. 먼저 누락 된 요소를 인쇄하면 누락 된 요소 중 가장 작은 요소가됩니다.

설명

입력 배열 :

    0 1 2 4 5

입력 배열에 알고리즘 적용,

남 = 5,

i = 0 인 경우

이진 검색 (0, 입력 배열) = True

i = 1 인 경우

이진 검색 (1, 입력 배열) = True

i = 2 인 경우

이진 검색 (2, 입력 배열) = True

i = 3 인 경우

이진 검색 (3, 입력 배열) = False

따라서 누락 된 최소 요소는 = 3입니다.

실시

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
// code for searching element is present in array or not
//using binary search
bool binary_search_missing(int arr[],int low,int high,int x)
{
  
  if(low > high)
  return false;
  
  int mid = low + (high - low)/2;
  if(arr[mid]==x)
    return true;
    
  else if(arr[mid] > x) 
    return binary_search_missing(arr,low,mid-1,x);
  else
    return binary_search_missing(arr,mid+1,high,x);
    
}
int main()
{
  
  int n,m;
  cin>>n>>m;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  for(int i=0;i<m;i++)
  {
    if(!binary_search_missing(a,0,n,i))
    {
      cout<<i;
      return 0;
    }
  }
  cout<<m;
  return 0;
}

자바 프로그램

import java.util.Scanner;
class sum
{
    public static int binary_search_missing(int arr[],int low,int high,int x)
    {
      if(low > high)
      return 0;
      int mid = low + (high - low)/2;
      if(arr[mid]==x)
        return 1;
      else if(arr[mid] > x) 
        return binary_search_missing(arr,low,mid-1,x);
      else
        return binary_search_missing(arr,mid+1,high,x);
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int temp=0;
        for(int i=0;i<m;i++)
        {
          if(binary_search_missing(arr,0,n,i)==0)
          {
            System.out.println(i);
            temp=1;
            i=n;
          }
        }
        System.out.println(m);
    }
}
9 15
0 1 2 3 4 5 6 7 8
9

복잡성 분석

시간 복잡성 – O (MlogN) 여기서 M은 요소의 범위이고 N은 배열의 크기입니다. 여기서 우리는 0에서 M까지의 범위에서 i의 모든 값을 검색 한 다음 O (mlogn) 시간 복잡도로 이어집니다.

공간 복잡성 – O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.

참조

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