លេខវិជ្ជមានតូចបំផុតដែលបាត់នៅក្នុងអារេដែលមិនបានតម្រៀប

សំណួរសំភាសន៍រចនាប្រព័ន្ធ អាចជាការបើកចំហរ ដូច្នេះវាពិបាកពេកក្នុងការដឹងពីវិធីត្រឹមត្រូវក្នុងការរៀបចំ។ ឥឡូវនេះខ្ញុំអាចបំបែកការរចនានៃ Amazon, Microsoft និង Adobe បន្ទាប់ពីទិញ សៀវភៅ​នេះ. ពិនិត្យឡើងវិញប្រចាំថ្ងៃ សំណួររចនា ហើយខ្ញុំសន្យាថាអ្នកអាចបំបែកការរចនាជុំ។

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងការមិនបានតម្រៀបដែលបានផ្តល់ឱ្យ អារេ រកឃើញលេខវិជ្ជមានតូចបំផុតដែលបាត់ក្នុងអារេដែលមិនបានតម្រៀប។ ចំនួនគត់វិជ្ជមានមិនរាប់បញ្ចូល ០ ទេ។ យើងអាចកែប្រែអារេដើមប្រសិនបើចាំបាច់។ អារេអាចមានលេខវិជ្ជមាននិងអវិជ្ជមាន។

ឧទាហរណ៍

a. ជួរបញ្ចូល៖ [៣, ៤, -3, ០, -២, ២, ១, ៧, ៨]

លទ្ធផល៖ ៥ ។
នៅក្នុងអារេដែលបានផ្តល់ឱ្យ 1,2,3,4 មានវត្តមានប៉ុន្តែ 5 អវត្តមានដែលជាចំនួនវិជ្ជមានតូចបំផុតដែលបាត់នៅក្នុងអារេដែលបានផ្តល់ឱ្យ។

b. ជួរបញ្ចូល៖ [២, ៣, ៧, ៨, -2, -២, ០]

លទ្ធផល៖ ៥ ។
នៅក្នុងអារេដែលបានផ្តល់ឱ្យ 1 គឺអវត្តមានដែលជាចំនួនវិជ្ជមានតូចបំផុតដែលបាត់នៅក្នុងអារេដែលបានផ្តល់ឱ្យ។

c. ជួរបញ្ចូល៖ [២, ៣, ៧, ៨, -2, -២, ០]

លទ្ធផល៖ ៥ ។
នៅក្នុងអារេដែលបានផ្តល់ឱ្យ 1 គឺអវត្តមានដែលជាចំនួនវិជ្ជមានតូចបំផុតដែលបាត់នៅក្នុងអារេដែលបានផ្តល់ឱ្យ។

ក្បួនដោះស្រាយសម្រាប់លេខវិជ្ជមានតូចបំផុតដែលបាត់នៅក្នុងអារេដែលមិនបានតម្រៀប

1. យើងត្រូវរកលេខវិជ្ជមានតូចបំផុតដែលបាត់ដូច្នេះយើងមិនត្រូវការលេខអវិជ្ជមានទេ។ ដូច្នេះយើងបង្កើតមុខងារដើម្បីផ្លាស់ទីលេខវិជ្ជមានទាំងអស់ទៅចុងបញ្ចប់នៃអារេហើយយើងរកឃើញលេខដែលបាត់នៅក្នុងអារេវិជ្ជមាន។

2. នៅក្នុងអនុគមន៍វិជ្ជមានវិជ្ជមាន

• យើងឆ្លងកាត់អារេដោយចង្អុលបង្ហាញពីរប្រសិនបើយើងរកឃើញលេខអវិជ្ជមានយើងប្តូរវាដោយទ្រនិចចាប់ផ្តើមហើយរំកិលទៅមុខ។
• យើងបន្តវារហូតដល់វាឈានដល់ចុងបញ្ចប់នៃអារេហើយយើងត្រឡប់សន្ទស្សន៍ចាប់ផ្តើមនៃអារេវិជ្ជមាន។ ដែលជាទីតាំងទ្រនិចចាប់ផ្តើមនៅពេលយើងឈានដល់ចុងបញ្ចប់នៃអារេ។

3. យើងបង្កើតមុខងារ FindMissingPostive ដែលយកអារេនិងទំហំនៃអារេហើយផ្តល់លេខដែលតូចបំផុត។

4. នៅក្នុងមុខងារនេះ

• ក។ នៅក្នុងអារេបញ្ចូលប្រសិនបើយើងរកឃើញចំនួនគត់វិជ្ជមានយើងសម្គាល់ឃើញថាវាបានទៅរកតម្លៃរបស់ខ្ញុំនៅទីតាំងសន្ទស្សន៍របស់វាទៅអវិជ្ជមាន។ ឧទាហរណ៍ៈប្រសិនបើអារេដែលបានផ្តល់គឺអារេ [] ។ ក្នុងអារេនេះប្រសិនបើយើងរកឃើញ ២ យើងធ្វើអារេ [១] = -២ ហើយបន្តរហូតដល់អារេបញ្ចប់ប្រសិនបើអារេ [i] - ១ <ទំហំនិងអារេ [អារេ [i] - ១]> ០ ។
• បន្ទាប់ពីកែប្រែអារេ។ ប្រសិនបើសន្ទស្សន៍ដែលយើងរកឃើញលេខវិជ្ជមានដំបូងគឺ k ។ បន្ទាប់មក k + 1 គឺជាលេខដែលបាត់ដែលតូចជាងគេ។ ប្រសិនបើយើងមិនបានរកឃើញលេខវិជ្ជមាននោះទំហំនៃអារេ + ១ គឺជាលេខដែលបាត់តូចជាងគេ។

5. សម្រាប់អារេបញ្ចូលដែលបានផ្តល់ឱ្យយើងដំបូងត្រូវអនុវត្តវិជ្ជមាន_arrayfunction (អនុញ្ញាតឱ្យវាត្រឡប់ 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;
}

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