정렬되지 않은 배열에서 누락 된 최소 양수

난이도 하드
자주 묻는 질문 수행자 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance 데이터 브릭 이베이 Facebook 팩트 셋 골드만 삭스 구글 JP 모건 Microsoft 모건 스탠리 (Morgan Stanley) 신탁 세일즈 포스 삼성 스냅 딜 텐센트 테슬라 씰룩 씰룩 움직이다 동네 짱 월마트 연구소 Wish
배열 Booking.com조회수 1186

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

문제 정책

주어진 정렬되지 않은 정렬 정렬되지 않은 배열에서 누락 된 가장 작은 양수를 찾습니다. 양의 정수는 0을 포함하지 않습니다. 필요한 경우 원래 배열을 수정할 수 있습니다. 배열에는 양수와 음수가 포함될 수 있습니다.

a. 입력 배열 : [3, 4, -1, 0, -2, 2, 1, 7, -8]

출력 : 5.
주어진 배열에서 1,2,3,4가 존재하지만 5는 존재하지 않습니다. 이는 주어진 배열에서 누락 된 가장 작은 양수입니다.

b. 입력 배열 : [2, 3, 7, 8, -1, -2, 0]

출력 : 1.
주어진 배열에서 1이 없습니다. 이는 주어진 배열에서 누락 된 가장 작은 양수입니다.

c. 입력 배열 : [2, 3, 7, 8, -1, -2, 0]

출력 : 1.
주어진 배열에서 1이 없습니다. 이는 주어진 배열에서 누락 된 가장 작은 양수입니다.

정렬되지 않은 배열에서 누락 된 최소 양수 알고리즘

1. 누락 된 가장 작은 양수를 찾아야하므로 음수가 필요하지 않습니다. 따라서 모든 양수를 배열 끝으로 이동하는 함수를 만들고 양수 배열에서 누락 된 숫자를 찾습니다.

2. positive_array 함수에서

  • 두 개의 포인터로 배열을 순회하고 음수를 찾으면 시작 포인터로 바꾸고 앞으로 이동합니다.
  • 배열의 끝에 도달 할 때까지 계속해서 양수 배열의 시작 인덱스를 반환합니다. 배열의 끝에 도달했을 때 시작 포인터 위치입니다.

3. 배열의 배열과 크기를 가져 와서 가장 작은 누락 된 수를 제공하는 FindMissingPostive 함수를 만듭니다.

4. 이 기능에서

  • ㅏ. 입력 배열에서 양의 정수를 찾으면 방문한 것으로 표시하여 인덱스 위치의 값을 음수로 만듭니다. 예 : 주어진 배열이 array [] 인 경우. 이 배열에서 2를 찾으면 array [i] – 1 <size 및 array [array [i] – 2]> 1 인 경우에만 array [1] = -0 등을 배열 끝까지 만듭니다.
  • 배열을 수정 한 후. 첫 번째 양수를 찾는 인덱스가 k이면. 그러면 k + 1은 가장 작은 결측 수입니다. 양수를 찾지 못했다면 배열의 크기 + 1이 가장 작은 누락 된 수입니다.

5. 주어진 입력 배열에 대해 먼저 positive_array 함수를 적용하고 (j를 반환하도록 함) FindMissingPostive를 (array + j)에 적용합니다.

실시

정렬되지 않은 배열에서 누락 된 최소 양수를위한 C ++ 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
 
//function to swap addresses
void swap(int *a, int *b)
{
    int temp = *a;
    *a   = *b;
    *b   = temp;
}
//In this function we move non-postive elements to the start of the array
//return the start index of start index of postive array
int positive_array(int array[], int N)
{
    int start_index = 0, i;
    for(i = 0; i < N; i++)
    {
       if (array[i] <= 0)  
       {
           swap(&array[i], &array[start_index]);
           start_index++;  // increment count of non-positive integers
       }
    }
    return start_index;
}
//In the given array this function finds the smallest missing number
//N is size of the array
//we mark the elements by making the elements at the postion(i-1)to negitive
//after modifying the array we find index at which we find first postive(j) and j+1 is the missing number.
int FindMissingPostive(int array[], int N)
{
  for(int i = 0; i < N; i++)
  {
    if(abs(array[i]) < N+1 && array[abs(array[i]) - 1] > 0)
    {
      array[abs(array[i]) - 1] = -array[abs(array[i]) - 1];
    }
  }
  for(int k = 0; k < N; k++){
    if (array[k] > 0)
    {
      return k+1;
    }
  }
  return N+1;
}
//insted of finding the missing postive integer in whole array
//we can find in postive part of the array fast.
int FindMissing(int array[], int N)
{
   int start = positive_array(array,N);
 
   return FindMissingPostive(array+start,N-start);
}
//main function to test above functions 
int main()
{
  int N;//size of the array
  cin>>N;
  int a[N];
  for(int i=0;i<N;i++)
  {
      cin>>a[i];
  }
  cout<<"smallest positive number missing: = "<<FindMissing(a,N);
  return 0;
}

정렬되지 않은 배열에서 누락 된 최소 양수를위한 Java 프로그램

import java.util.Scanner;

class sum
{
    public static int abs(int x)
    {
        if(x<0)
        {
            return -1*x;
        }
        else
        {
            return x;
        }
    }
    //In this function we move non-postive elements to the start of the array
    //return the start index of start index of postive array
    public static int positive_array(int array[], int N)
    {
        int start_index = 0, i;
        for(i = 0; i < N; i++)
        {
           if (array[i] <= 0)  
           {
               swap(array[i], array[start_index]);
               start_index++;  // increment count of non-positive integers
           }
        }
        return start_index;
    }
    //In the given array this function finds the smallest missing number
    //N is size of the array
    //we mark the elements by making the elements at the postion(i-1)to negitive
    //after modifying the array we find index at which we find first postive(j) and j+1 is the missing number.
    public static int FindMissingPostive(int array[], int N)
    {
      for(int i = 0; i < N; i++)
      {
        if(abs(array[i]) < N+1 && array[abs(array[i]) - 1] > 0)
        {
          array[abs(array[i]) - 1] = -array[abs(array[i]) - 1];
        }
      }
      for(int k = 0; k < N; k++){
        if (array[k] > 0)
        {
          return k+1;
        }
      }
      return N+1;
    }
    //insted of finding the missing postive integer in whole array
    //we can find in postive part of the array fast.
    public static int FindMissing(int array[], int N)
    {
       int start = 0;
        for(int i = 0; i < N; i++)
        {
           if (array[i] <= 0)  
           {
               array[i]=array[i]+array[start]-(array[start]=array[i]);
               start++;  // increment count of non-positive integers
           }
        }
       int temp[] = new int[N-start];
       for(int i=0;i<N-start;i++)
       {
           temp[i]=array[i+start];
       }
       return FindMissingPostive(temp,N-start);
    }
    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();
        }
        System.out.println("smallest positive number missing: = "+FindMissing(a,n));
    }
}
9
3 4 -1 0 -2 2 1 7 -8
smallest positive number missing: = 5

복잡성 분석

시간 복잡성

O (N) 여기서 n은 주어진 배열의 크기입니다. 여기서 우리는 배열을 한 번만 순회하고 가장 작은 양의 결측 수를 얻었습니다.

공간 복잡성

O (1) 여기에서는 몇 가지 변수를 사용하여 답을 계산하기 때문입니다.

참조

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