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

កម្រិតលំបាក រឹង
សួរញឹកញាប់ គួរឱ្យគោរព កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg ByteDance មូលដ្ឋានទិន្នន័យ របស់ eBay Facebook រោងចក្រ ក្រុមហ៊ុន Goldman Sachs ក្រុមហ៊ុន google ដោយឡែកក្រុមហ៊ុន JP Morgan ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Morgan Stanley ក្រុមហ៊ុន Oracle ការលក់ ក្រុមហ៊ុន Samsung Snapdeal ក្រុមហ៊ុន Tencent ក្រុមហ៊ុន tesla Twitch Uber បន្ទប់ពិសោធន៍វ៉លម៉ាត សូមជូនពរ
អារេ Booking.comចំនួនមើល 1200

សំណួរសំភាសន៍រចនាប្រព័ន្ធ អាចជាការបើកចំហរ ដូច្នេះវាពិបាកពេកក្នុងការដឹងពីវិធីត្រឹមត្រូវក្នុងការរៀបចំ។ ឥឡូវនេះខ្ញុំអាចបំបែកការរចនានៃ 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

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

អូរ (n) ដែល n ជាទំហំនៃអារេដែលបានផ្តល់។ នៅទីនេះយើងឆ្លងកាត់អារេតែមួយដងហើយទទួលបានលេខដែលបាត់វិជ្ជមានតិចតួចបំផុត។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១) ពីព្រោះនៅទីនេះយើងប្រើអថេរខ្លះដើម្បីគណនាចម្លើយ។

ឯកសារយោង

បទសម្ភាសន៍រចនាប្រព័ន្ធបំបែក
Translate »