Չհավաքված զանգվածում բացակայում է ամենափոքր դրական թիվը


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Ակոլիտ Adobe Amazon խնձոր Bloomberg ByteDance Տվյալների շտեմարաններ eBay facebook Փաստեր Goldman Sachs-ը Google JP Morgan Microsoft Morgan Stanley Պատգամախոս Salesforce Samsung Snapdeal Tencent Tesla Ջղաձգություն Uber Walmart Labs Ցանկություն
Դասավորություն Booking.com

Խնդիրի հայտարարություն

Տրված չհավաքվածում դասավորություն գտնել չտեսակված զանգվածում բացակայող ամենափոքր դրական թիվը: Դրական ամբողջ թիվը չի պարունակում 0: Անհրաժեշտության դեպքում մենք կարող ենք փոփոխել բնօրինակ զանգվածը: Rayանգվածը կարող է պարունակել դրական և բացասական թվեր:

Օրինակ

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. Դրական_ զանգվածի գործառույթում

  • Մենք զանգվածը հատում ենք երկու ցուցիչով, եթե գտնենք բացասական թիվ, այն փոխում ենք մեկնարկի ցուցիչով և տեղափոխում այն ​​առաջ:
  • Մենք շարունակում ենք դա այնքան ժամանակ, քանի դեռ այն չի հասել զանգվածի ավարտին և մենք վերադարձնում ենք դրական զանգվածի մեկնարկի ցուցիչը: Ո՞րն է մեկնարկի ցուցիչի դիրքը, երբ հասնում ենք զանգվածի ավարտին:

3. Մենք ստեղծում ենք FindMissingPostive գործառույթ, որը վերցնում է զանգվածի զանգվածն ու չափը և տալիս բացակայող ամենափոքր թիվը:

4. Այս գործառույթում

  • ա Մուտքային զանգվածում, եթե գտնում ենք դրական ամբողջ թիվ, նշում ենք, որ այն այցելել է իմ ՝ արժեքը դարձնելով իր ինդեքսի դիրքում բացասական: Օրինակ. Եթե տրված զանգվածը զանգված է []: Այս զանգվածում, եթե գտնենք 2, մենք զանգված ենք կազմում [1] = -2 և այսպես շարունակ, մինչ զանգվածի ավարտը միայն եթե զանգվածը [i] - 1 <չափը և զանգվածը [զանգվածը [i] - 1]> 0:
  • Զանգվածը փոփոխելուց հետո: Եթե ​​ցուցանիշը, որով մենք գտնում ենք առաջին դրական թիվը, k է: Ապա k + 1 - ը բացթողման ամենափոքր թիվն է: Եթե ​​մենք այն ժամանակ դրական թիվ չգտանք, զանգվածի + 1 չափը բացթողման ամենափոքր թիվն է:

5. Տրված մուտքային զանգվածի համար մենք նախ կիրառում ենք positive_arrayfunction (թող վերադառնա 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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n) որտեղ n- ը տրված զանգվածի չափն է: Այստեղ մենք զանգվածը հատում ենք միայն մեկ անգամ և ստանում ամենափոքր դրական բացակայող թիվը:

Տիեզերական բարդություն

Ո (1) քանի որ այստեղ մենք օգտագործում ենք որոշ փոփոխականներ պատասխանը հաշվարկելու համար:

Սայլակ