Unsorted Array တစ်ခုတွင်ပျောက်ဆုံးနေသောအနည်းဆုံးအပြုသဘောဆောင်သောနံပါတ်  


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် တိကျသော Adobe က အမေဇုံ Apple ဘလွန်းဘာ့ဂ် ByteDance Databricks ကို eBay Facebook က အချက်အလက် Goldman Sachs Google JP Morgan Microsoft က မော်ဂန်စတန်လေ Oracle က Salesforce Samsung Snapdeal Tencent တက်စလာ Twitch Uber Walmart ဓာတ်ခွဲခန်းများ ဆုတောင်း
အခင်းအကျင်း Booking.com

ပြProbleနာဖော်ပြချက်  

ပေးထားသော unsorted ၌တည်၏ အခင်းအကျင်း unorted ခင်းကျင်းထဲမှာပျောက်ဆုံးနေတဲ့အသေးငယ်ဆုံးအပြုသဘောဆောင်တဲ့နံပါတ်ကိုရှာပါ။ အပြုသဘောဆောင်တဲ့ကိန်းတစ်ခုမှာ 0. မပါဝင်ဘူး။ လိုအပ်လျှင်မူရင်း array ကိုပြုပြင်နိုင်သည်။ Array တွင်အပေါင်းနှင့်အနှုတ်လက္ခဏာများပါနိုင်သည်။

နမူနာ  

a. input array: [၃၊ ၄၊ ၁၊ ၀၊ ၂၊ ၂၊ ၁၊ ၇၊ -3]

ရလဒ် ၅ ။
ပေးထားသောခင်းကျင်းချက်တွင် 1,2,3,4 ရှိသည်။ သို့သော် ၅ ခုသည်မရှိတော့ပါ၊ ၎င်းသည်ပေးထားသောခင်းကျင်းထဲ၌ပျောက်ဆုံးနေဆုံးသောအငယ်ဆုံးဖြစ်သည်။

b. input array: [၂၊ ၃၊ ၇၊ ၈၊ ၁၊ ၂၊ ၀]

ရလဒ် ၅ ။
ပေးထားသောခင်းကျင်းမှုထဲတွင် ၁ ခုမှာမရှိတော့ဘဲ၎င်းသည်ပေးထားသောခင်းကျင်းထဲ၌ပျောက်ဆုံးနေဆုံးသောအငယ်ဆုံးဖြစ်သည်။

c. input array: [၂၊ ၃၊ ၇၊ ၈၊ ၁၊ ၂၊ ၀]

ရလဒ် ၅ ။
ပေးထားသောခင်းကျင်းမှုထဲတွင် ၁ ခုမှာမရှိတော့ဘဲ၎င်းသည်ပေးထားသောခင်းကျင်းထဲ၌ပျောက်ဆုံးနေဆုံးသောအငယ်ဆုံးဖြစ်သည်။

Unsorted Array တစ်ခုတွင်ပျောက်ဆုံးနေသောအသေးဆုံးအပြုသဘောဆောင်သောနံပါတ်အတွက် Algorithm  

1. အငယ်ဆုံးပျောက်ဆုံးနေတဲ့အပြုသဘောဆောင်တဲ့ကိန်းကိုရှာဖို့လိုတယ်။ ဒါကြောင့်၊ ကျွန်တော်တို့ကအပြုသဘောဆောင်တဲ့ကိန်းဂဏန်းများအားလုံးကို array ရဲ့အဆုံးဆီရွှေ့ဖို့ function တစ်ခုဖန်တီးတယ်။

2. positive_array လုပ်ဆောင်ချက်မှာ

  • ကျွန်ုပ်တို့သည် array ကိုအမှတ်အသားနှစ်မျိုးဖြင့်ဖြတ်သန်းသွားသည်။ အနုတ်လက္ခဏာနံပါတ်ကိုတွေ့ရှိပါက၎င်းသည် start pointer ဖြင့်လဲကာရှေ့သို့ရွေ့သည်။
  • ၎င်းသည် array ၏အဆုံးသို့ရောက်ရှိသည်အထိဆက်လက်လုပ်ဆောင်ပြီးအပြုသဘောခင်းကျင်းမှု၏ start index ကိုပြန်ပို့ပါမည်။ ကျနော်တို့ကခင်းကျင်း၏အဆုံးကိုရောက်ရှိသည့်အခါက start pointer အနေအထား, ဘယ်ဖြစ်ပါတယ်။
လည်းကြည့်ရှုပါ
Palindrome permutation

3. FindMissingPostive function ကိုကျွန်ုပ်တို့ဖန်တီးသည်။ ၎င်းသည် array ၏အရွယ်အစားနှင့်အရွယ်အစားကိုယူပြီးအနည်းဆုံးပျောက်ဆုံးသောနံပါတ်ကိုပေးသည်။

4. ဒီလုပ်ဆောင်ချက်မှာ

  • က။ input array ထဲမှာ၊ အပြုသဘောဆောင်တဲ့ကိန်းတစ်ခုရှာတွေ့ရင်၊ ကျွန်တော်တန်ဖိုးကိုသူ့ရဲ့ index အနေအထားမှာအနှုတ်အဖြစ်ပြောင်းသွားတာကိုအမှတ်အသားပြုသည်။ ဥပမာ: ပေးထားသောခင်းကျင်းခင်းကျင်းပါလျှင် [] ။ ဒီခင်းကျင်းမှုတွင် 2 ကိုတွေ့လျှင် array [1] = -2 နှင့် array ကိုအဆုံးသတ်သည်အထိ array [i] - 1 <size and array [array [i] - 1]> 0) ပြုလုပ်သည်။
  • အဆိုပါခင်းကျင်းပြုပြင်မွမ်းမံပြီးနောက်။ ကျနော်တို့ပထမ ဦး ဆုံးအပြုသဘောဆောင်သောကိန်းကိုရှာဖွေသည့်မှာအညွှန်းကိန်း k လျှင်။ ထိုအခါ k + 1 သည်အငယ်ဆုံးပျောက်ဆုံးသောနံပါတ်ဖြစ်သည်။ အကယ်၍ ကျွန်ုပ်တို့သည်အပြုသဘောဆောင်သောကိန်းကိုရှာမတွေ့ပါက array + ၏အရွယ်အစားသည်အငယ်ဆုံးပျောက်ဆုံးနေသောနံပါတ်ဖြစ်သည်။

5. ပေးထားသော input array အတွက်ကျွန်ုပ်တို့သည် positive_arrayfunction ကို (၎င်းကိုပြန်သွားပါစေ) ပထမ ဦး စွာလျှောက်ထားပြီး FindMissingPostive (array + j) ကိုအသုံးချပါ။

အကောင်အထည်ဖော်ရေး  

Unsorted Array တစ်ခုတွင်ပျောက်ဆုံးနေတဲ့အငယ်ဆုံး Positive Number အတွက် C ++ Program

#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;
}

Unsorted Array တစ်ခုတွင်ပျောက်ဆုံးနေသောအသေးဆုံးအပြုသဘောဆောင်သောနံပါတ်အတွက် Java Program

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 ပေးထားသောခင်းကျင်း၏အရွယ်အစားသည်။ ဤတွင်ကျွန်ုပ်တို့သည်ခင်းကျင်းမှုကိုတစ်ကြိမ်သာဖြတ်သန်းခဲ့ပြီးအသေးငယ်ဆုံးအပြုသဘောပျောက်ဆုံးနေသောနံပါတ်ကိုရရှိခဲ့သည်

လည်းကြည့်ရှုပါ
ထပ်ခါတလဲလဲ Subarray ၏အမြင့်ဆုံးအရှည်

အာကာသရှုပ်ထွေးမှု

အို (၁) ဘာဖြစ်လို့လဲဆိုတော့ဒီမှာကျွန်တော်တို့ကအဖြေကိုတွက်ချက်ဖို့ variable တွေကိုသုံးတယ်။

ကိုးကား