کوچکترین شماره گمشده را در یک آرایه مرتب شده پیدا کنید


سطح دشواری ساده
اغلب در خشت آمازون سیب بلومبرگ یکی از سرمایه سیسکو ای بی فیس بوک گلدمن ساکس گوگل آی بی ام JP مورگان مایکروسافت کارت گرافیک Nvidia وحی پی پال ServiceNow Yandex
شبکه های Arista صف ریاضی

بیان مسأله

در مسئله "یافتن کمترین شماره گمشده در یک آرایه مرتب شده" ما یک آرایه صحیح داده ایم. کمترین تعداد گمشده را در مرتب سازی به اندازه 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 برای یافتن کوچکترین شماره گمشده در یک آرایه مرتب شده

در اینجا ما از مفهوم جستجوی دودویی استفاده می کنیم زیرا آرایه قبلا مرتب شده است. در اینجا ما هر مقدار i را در محدوده 0 تا M جستجو می کنیم. اگر عنصر پیدا نشد ، آن عنصر را چاپ کرده و برگردانید.

الگوریتم

  1. یک حلقه را از 0 به M-1 اجرا کنید و انجام دهید
  2. جستجوی دودویی برای هر عنصر در محدوده و بررسی اینکه آیا شماره وجود دارد یا خیر.
  3. [0,1,2,4,5,6,7,8،0،8،0،8،XNUMX،XNUMX،XNUMX] آرایه داده شده است ، بنابراین در اینجا دامنه XNUMX تا XNUMX است. جستجوی دودویی برای هر عدد از XNUMX تا XNUMX در آرایه.
  4. ابتدا عنصری را که گم شده است چاپ کنید ، این کوچکترین عنصر گمشده خواهد بود.

توضیح

آرایه ورودی:

    01245

الگوریتم را روی آرایه ورودی اعمال کنید ،

M = 5 ،

برای i = 0 ،

جستجوی دودویی (0 ، آرایه ورودی) = درست است

برای i = 1 ،

جستجوی دودویی (1 ، آرایه ورودی) = درست است

برای i = 2 ،

جستجوی دودویی (2 ، آرایه ورودی) = درست است

برای i = 3 ،

جستجوی دودویی (3 ، آرایه ورودی) = نادرست است

بنابراین ، کوچکترین عنصر از دست رفته = 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 به اندازه آرایه است. در اینجا ما هر مقدار i را در محدوده 0 تا M جستجو می کنیم سپس ما را به پیچیدگی زمان O (mlogn) می رساند.

پیچیدگی فضا - O (1) زیرا ما در اینجا از هیچ فضای کمکی استفاده نمی کنیم.

منابع