ពិនិត្យមើលថាតើអារេផ្ទុកនូវចំនួនគត់ដែលជាប់គ្នាជាមួយច្បាប់ចម្លងដែលបានអនុញ្ញាត


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ Accenture ក្រុមហ៊ុន Amazon Directi Facebook វិចារណញាណ
អារេ ហាស់ ខ្សែអក្សរ

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

ឧទាហរណ៍

ការបញ្ចូលគំរូ៖

[១, ៤, ៦, ២, ១]

លទ្ធផលគំរូ៖

បាទ

ការពន្យល់:

វាមានសំណុំនៃចំនួនគត់ជាប់គ្នានៃលេខ [2, 3, 4, 1]

ក្បួនដោះស្រាយដើម្បីពិនិត្យមើលថាតើអារេមានចំនួនគត់ជាប់គ្នាជាមួយលេខស្ទួនត្រូវបានអនុញ្ញាត

1. Declare a Set.
2. Add all the elements of an array into the Set.
3. Set count to 1 and currentElement to arr[0]-1.
4. Open a loop, while Set contains the currentElement.
  1. Do count++ and currentElement--.
5. Set currentElement to arr[0]+1.
6. Open a loop, while Set contains the currentElement.
  1. Do count++ and currentElement++.
7. Check if the count is equal to the size of a set, if condition satisfies, then return true.
8. Else return false.

ការពន្យល់

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

យើងនឹងបញ្ចូលធាតុទាំងអស់ដោយឆ្លងកាត់អារេ កំណត់ ហើយវានឹងមានធាតុប្លែកៗឥឡូវនេះ។ កំណត់តម្លៃនៃការរាប់ទៅ 1 ហើយយើងនឹងបន្តបង្កើនវានៅក្នុងប្រតិបត្តិការនៅពេលក្រោយ។ វានឹងពិនិត្យមើលទំហំនៃសំណុំជាប់គ្នានៃចំនួនគត់ព្រោះវានឹងមានទំហំខុសពីការកំណត់ប្រសិនបើមិនមានចំនួនគត់ជាប់គ្នាមាននៅក្នុងអារេ។ ការមកដល់ [០] -១ នឹងជាតម្លៃនៃចរន្តបន្ថែម។ វានឹងរក្សាភ្នែកលើសំណុំនៃ ចំនួនគត់.

បើករង្វិលជុំហើយវានឹងបន្តរហូតដល់កំណត់មានចរន្តបន្ថែមនៅក្នុងវាពីព្រោះនៅក្នុងរង្វិលជុំមួយយើងនឹងបង្កើនតម្លៃនៃការរាប់ដោយ ១ (រាប់ = រាប់ + ១) និងបន្ថយតម្លៃនៃការបន្ថែមដោយ ១ (currentElement = currentElement) - ១) ។ កំណត់តម្លៃនៃការបន្ថែមដើម្បីឈានដល់ [1] +1 ហើយបើករង្វិលជុំមួយទៀតហើយវានឹងបន្តរហូតដល់កំណត់មានចរន្តបន្ថែមនៅក្នុងវាប៉ុន្តែពេលនេះយើងនឹងបង្កើនតម្លៃទាំងពីរដោយ 1 រាប់ ++ និង currentElement ++ ។ នៅចុងបញ្ចប់យើងនឹងពិនិត្យមើលថាតើតម្លៃនៃការរាប់ស្មើនឹងទំហំនៃសំណុំប្រសិនបើវាត្រូវបានគេរកឃើញថាជាការពិតបន្ទាប់មកត្រឡប់ពិតផ្សេងទៀតមិនពិត។

ចូរយើងពិចារណាឧទាហរណ៍មួយ៖

ឧទាហរណ៍

មកដល់ [] = {៥, ២, ៣, ៦, ៤, ៤, ៦, ៦};

បន្ទាប់ពីឆ្លងកាត់អារេយើងនឹងមានតម្លៃដូចខាងក្រោមនៅក្នុងសំណុំ។

កំណត់ៈ {2,3,4,5,6}, ដូចដែលវាដកធាតុស្ទួនចេញ

រាប់ = 1, currentElement = មកដល់ [0] -1 = 4;

  • ខណៈពេលដែលសំណុំមានបច្ចុប្បន្នបន្ថែម (៤) គឺពិត

រាប់ = រាប់ + 1 => រាប់ = ២, currentElement– => currentElement = ៣

  • ខណៈពេលដែលសំណុំមានបច្ចុប្បន្នបន្ថែម (៤) គឺពិត

រាប់ = រាប់ + 1 => រាប់ = ២, currentElement– => currentElement = ៣

  • ខណៈពេលដែលសំណុំមានបច្ចុប្បន្នបន្ថែម (៤) គឺពិត

រាប់ = រាប់ + 1 => រាប់ = ២, currentElement– => currentElement = ៣

  • ខណៈពេលដែលសំណុំមានចរន្តបន្ថែម (១) គឺមិនពិតដូច្នេះវាចេញពីរង្វិលជុំ។

កំណត់ currentElement [0] = មកដល់ [0] +1 => currentElement = ៦

  • ខណៈពេលដែលសំណុំមានបច្ចុប្បន្នបន្ថែម (៤) គឺពិត

រាប់ = រាប់ + 1 => រាប់ = 5, currentElement ++ => currentElement = 7

  • ខណៈពេលដែលសំណុំមានចរន្តបន្ថែម (៧) គឺមិនពិតដូច្នេះវាចេញពីរង្វិលជុំ

ហើយវានឹងពិនិត្យមើលថាតើការរាប់ស្មើនឹងទំហំនៃសំណុំនិងលក្ខខណ្ឌ័ពេញចិត្តដូច្នេះវានឹងត្រលប់ជាការពិតហើយនៅក្នុងមុខងារសំខាន់ yes នឹងត្រូវបានបោះពុម្ព។

ការអនុវត្តន៍

លេខកូដ C ++ ដើម្បីពិនិត្យមើលថាតើអារេមានចំនួនគត់ជាប់គ្នាជាមួយលេខស្ទួនត្រូវបានអនុញ្ញាត

#include<iostream>
#include<unordered_set>
using namespace std;
bool areElementsContiguous(int arr[], int n)
{
    unordered_set<int> Set;
    for (int i = 0; i < n; i++)
        Set.insert(arr[i]);

    int count = 1;
    int currentElement = arr[0] - 1;
    while (Set.find(currentElement) != Set.end())
    {
        count++;
        currentElement--;
    }
    currentElement = arr[0] + 1;
    while (Set.find(currentElement) != Set.end())
    {
        count++;
        currentElement++;
    }
    return (count == (int)(Set.size()));
}
int main()
{
    int arr[] = { 5, 2, 3, 6, 4, 4, 6, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (areElementsContiguous(arr, n))
        cout << "Yes, it is set of contiguous integers.";
    else
        cout << "No, it is not a set of contiguous integers.";
    return 0;
}
Yes, it is set of contiguous integers.

កូដចាវ៉ាដើម្បីពិនិត្យមើលថាតើអារេមានចំនួនគត់ជាប់គ្នាដែលមានច្បាប់ចម្លងត្រូវបានអនុញ្ញាត

import java.util.HashSet;
class contiguousArray
{
    public static Boolean checkContiguousElements(int arr[], int n)
    {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < n; i++)
        {
            set.add(arr[i]);
        }
        int count = 1;
        int currentElement = arr[0] - 1;
        while (set.contains(currentElement) == true)
        {
            count++;
            currentElement--;
        }
        currentElement = arr[0] + 1;
        while (set.contains(currentElement) == true)
        {
            count++;
            currentElement++;
        }
        return (count == (set.size()));
    }
    public static void main(String[] args)
    {
        int arr[] = { 10, 7, 8, 11, 9, 9, 10, 10 };
        int n = arr.length;
        if (checkContiguousElements(arr, n))
            System.out.println("Yes, it is set of contiguous integers.");
        else
            System.out.println("No, it is not a set of contiguous integers.");
    }
}
Yes, it is set of contiguous integers.

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

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

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។

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

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។