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

자바 프로그램

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) 여기에 보조 공간을 사용하지 않기 때문입니다.

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

설명

입력 배열 :

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

남 = 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