រកឃើញធាតុដែលបាត់នៃជួរមួយ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ដេលីវ៉ាយ GreyOrange LinkedIn ណាហ្គារ៉ូ ល្ខោនអូប៉េរ៉ា Synopsys
ហាស់ ឡាសាននិងធូបូ តម្រៀប

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

ឧទាហរណ៍

រកឃើញធាតុដែលបាត់នៃជួរមួយ

arr[] = [1, 3, 5, 7, 8, 9]

low=1 high = 10
2, 4, 6, 10

ការពន្យល់

ទាំងនេះគឺជាលេខដែលបាត់នៅក្នុងអារេនៅក្នុងជួរដែលបានផ្តល់ឱ្យទាបនិងខ្ពស់ពោលគឺលេខ ១ និង ១០ ។

arr[] = [2, 3, 7, 8]

low=1 high = 9
1, 4, 5, 6, 9

ការពន្យល់

ទាំងនេះគឺជាលេខដែលបាត់នៅក្នុងអារេនៅក្នុងជួរដែលបានផ្តល់ឱ្យទាបនិងខ្ពស់ពោលគឺលេខ ១ និង ១០ ។

ក្បួនដោះស្រាយ

  1. ប្រកាសក សំណុំ.
  2. ឆ្លងកាត់អារេហើយដាក់ធាតុទាំងអស់ទៅក្នុងសំណុំ។
  3. ខណៈពេលដែល“ i” ស្មើនឹងទាបហើយ“ i” គឺទាបជាងខ្ពស់។
    • ប្រសិនបើឈុតមួយមិនមាន“ i” ។
      • បោះពុម្ព 'i' ។

ការពន្យល់

យើងត្រូវបានផ្តល់របាយការណ៍បញ្ហាដែលស្នើសុំឱ្យរកឃើញធាតុដែលបាត់ទាំងអស់នៅក្នុងអារេមួយនៅក្នុងជួរដែលបានផ្តល់ឱ្យទាបនិងខ្ពស់។ ដើម្បីដោះស្រាយបញ្ហានេះយើងនឹងប្រើសំណុំមួយហើយយើងនឹងរក្សាទុកតម្លៃទៅក្នុងសំណុំនៃអារេដែលបានផ្តល់ឱ្យ។ យើងត្រូវបានគេផ្តល់ជួរថាទាបនិងខ្ពស់យើងត្រូវបោះពុម្ពធាតុទាំងអស់ក្នុងកំរិតទាបនិងខ្ពស់។

ដើម្បីទទួលបានការបញ្ជាទិញនោះយើងរក្សាទុកធាតុអារេទៅក្នុងសំណុំរួចហើយ។ យើងត្រូវដំណើរការរង្វិលជុំដែលចាប់ផ្តើម 'i' ទាប។ យើងដំណើរការរង្វិលជុំរហូតដល់តម្លៃ 'i' ខ្ពស់។ បន្ទាប់មកពិនិត្យមើលថាតើសំណុំមិនមានតំលៃ 'i' បន្ទាប់មកបោះពុម្ព 'i' ។ ដូច្នេះយើងនឹងទទួលបានធាតុទាំងអស់ដែលបាត់ពីអារេមួយនៅក្នុងជួរដែលបានផ្តល់។ ចូរយើងពិចារណាឧទាហរណ៍មួយ។

មកដល់ [] = {២, ៣, ៧, ៨} ទាប = ១, ខ្ពស់ = ៩

យើងត្រូវឆ្លងកាត់អារេហើយដាក់ធាតុទាំងអស់នៃអារេទៅក្នុងសំណុំ។ ឈុតរបស់យើងនឹងក្លាយជា

សំណុំ = [2,3,7,8]

នៅក្នុងរង្វិលជុំចាប់ផ្តើមអាយទៅទាបហើយរង្វិលជុំដំណើរការរហូតដល់ខ្ពស់វាមានន័យថា 'i' ស្មើនឹងកំរិតទាប = 1 និងខ្ពស់ = 9

i = 1, ប្រសិនបើឈុតមិនមានខ្ញុំ, បោះពុម្ព 1

[១៩៤៥៩១២២]

i = 2, សំណុំមានតម្លៃ '2' ហើយមិនធ្វើអ្វីទាំងអស់។

i = 3, សំណុំមានតម្លៃ '3' ហើយមិនធ្វើអ្វីទាំងអស់។

i = 4, ប្រសិនបើឈុតមិនមានខ្ញុំ, បោះពុម្ព 4

[1, 4]

i = 5, ប្រសិនបើឈុតមិនមានខ្ញុំ, បោះពុម្ព 5

[1, 4, 5]

i = 6, ប្រសិនបើឈុតមិនមានខ្ញុំ, បោះពុម្ព 6

[៣៤, ៨៦, ៨៧, ៧៦៥]

i = 7, សំណុំមានតម្លៃ '7' ហើយមិនធ្វើអ្វីទាំងអស់។

i = 8, សំណុំមានតម្លៃ '8' ហើយមិនធ្វើអ្វីទាំងអស់។

i = 9, ប្រសិនបើឈុតមិនមានខ្ញុំ, បោះពុម្ព 1

[៥, ៤, ៣, ២, ១]

លទ្ធផលរបស់យើងនឹងក្លាយជាៈ [១, ៤, ៥, ៦, ៩]

លេខកូដ

កូដ C ++ ដើម្បីស្វែងរកធាតុដែលបាត់

#include <unordered_set>
#include<iostream>

using namespace std;

void getMissingElements(int arr[], int n, int low, int high)
{
    unordered_set<int> myset;
    for (int i = 0; i < n; i++)
        myset.insert(arr[i]);

    for (int x = low; x <= high; x++)
        if (myset.find(x) == myset.end())
            cout << x << " ";
}
int main()
{
    int arr[] = { 2,3,7,8 };
    int low = 1, high = 9;
    int n = sizeof(arr) / sizeof(arr[0]);
    getMissingElements(arr, n, low, high);
    return 0;
}
1 4 5 6 9

កូដចាវ៉ាដើម្បីស្វែងរកធាតុដែលបាត់នៃជួរ

import java.util.HashSet;

class RangeMissingElements
{
    public static void getMissingElements(int arr[], int low, int high)
    {
        HashSet<Integer> myset = new HashSet<>();

        for (int i = 0; i < arr.length; i++)
        {
            myset.add(arr[i]);
        }

        for (int i = low; i <= high; i++)
        {
            if (!myset.contains(i))
            {
                System.out.print(i + " ");
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,7,8};
        int low = 1, high = 9;
        getMissingElements(arr, low, high);
    }
}
1 4 5 6 9

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

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

O (n + (ខ្ពស់ទាប + ១)) ដែលជាកន្លែងដែល “ n” គឺជាចំនួននៃធាតុដែលមាននៅក្នុងអារេ "ខ្ពស់" និង “ ទាប” គឺជាធាតុបញ្ចូលដែលបានផ្តល់។

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

អូ (n), ក្នុងករណីអាក្រក់បំផុតប្រសិនបើធាតុទាំងអស់ខុសគ្នា។ យើងនឹងត្រូវរក្សាទុកធាតុទាំងអស់។ ដូច្នេះការធ្វើឱ្យក្បួនដោះស្រាយត្រូវការពេលវេលាលីនេអ៊ែរ។