Сұрыпталмаған массивтегі ең кіші оң сан


Күрделілік дәрежесі қиын
Жиі кіреді Акколит Adobe Amazon алма Bloomberg ByteDance Мәліметтер базасы еВау Facebook Деректер жинағы Голдман Сакс Google JP Morgan Microsoft Морган Стэнли Oracle Salesforce Samsung Шапшаң Tencent Tesla Twitch қиятын Walmart зертханалары тілек
Array Booking.com

Проблемалық мәлімдеме

Берілгенде сұрыпталмаған массив сұрыпталмаған массивте жоқ ең кіші оң санды табыңыз. Натурал санға 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. Оң_аралар функциясында,

  • Біз массивті екі көрсеткішпен өткіземіз, егер теріс сан тапсақ, оны старт көрсеткішімен ауыстырып, алға жылжытыңыз.
  • Біз оны массивтің соңына жеткенше жалғастырамыз және оң массивтің басталу индексін қайтарамыз. Біз массивтің соңына жеткенде сілтегіштің қай позициясы болады.

3. Біз жиым мен массивтің өлшемін қабылдайтын және жетіспейтін ең кіші санды беретін FindMissingPostive функциясын құрамыз.

4. Бұл функцияда,

  • а. Кіріс массивінде, егер біз оң бүтін санды тапсақ, мен оны индекс жағдайындағы мәнді теріс мәнге айналдырған деп белгілейміз. Мысалы: егер берілген жиым [] массиві болса. Бұл массивте, егер біз 2 тапсақ, [1] = -2 массивін және т.с.с. массивтің соңына дейін [i] - 1 <массиві және [массив [i] - 1]> 0 болған жағдайда ғана жасаймыз.
  • Массивті өзгерткеннен кейін. Егер бірінші оң санды табатын көрсеткіш k болса. Онда k + 1 - жоғалған ең кіші сан. Егер оң санды таппасақ, онда + 1 массивінің өлшемі жетіспейтін ең кіші сан болып табылады.

5. Берілген кіріс массиві үшін біз алдымен оң_аралықфункцияны қолданамыз (оны j қайтарсын) және FindMissingPostive-ді (жиым + 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) өйткені мұнда жауапты есептеу үшін кейбір айнымалыларды қолданамыз.

Әдебиеттер тізімі