Массивтің қайталанатын рұқсат етілген іргелес бүтін сандар бар-жоғын тексеріңіз


Күрделілік дәрежесі орта
Жиі кіреді Accenture Amazon Directi Facebook Intuit
Array Hash String

Сізге ан массив құрамында қайталанатын элементтер болуы мүмкін бүтін сандар. Проблемалық мәлімдеме оның іргелес бүтін сандар жиынтығы екенін білуді сұрайды, егер бар болса «Иә», егер жоқ болса, «Жоқ» деп басады.

мысал

Үлгі енгізу:

[2, 3, 4, 1, 7, 9]

Мысал шығару:

иә

Түсіндіру:

Онда [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-ге теңестіріңіз, сонан кейін оны көбейтуді жалғастырамыз. Ол бүтін сандардың жиынтығының өлшемін тексереді, өйткені егер жиымға тұтас сандар болмаса, ол Set-тен өзгеше болады. Arr [0] -1 currentElement мәні болады. Бұл жиынтығын қадағалап отырады бүтін сандар.

Циклды ашыңыз және ол Set құрамында ағымдық элемент бар болғанға дейін жалғасады, өйткені циклде біз санау мәнін 1-ге арттырамыз (count = count + 1) және currentElement мәнін 1-ге төмендетеміз (currentElement = currentElement - 1). CurrentElement мәнін arr [0] +1 етіп орнатыңыз және басқа циклды ашыңыз, сонда ол SetElement элементінде болғанға дейін жалғасады, бірақ бұл кезде мәндерді 1 count ++ және currentElement ++ мәндеріне көбейтеміз. Ақыр соңында, санау мәні Set өлшеміне тең екендігін тексереміз, егер ол дұрыс деп табылса, онда return true else return false мәнін қайтарамыз.

Мысалды қарастырайық:

мысал

arr [] = {5, 2, 3, 6, 4, 4, 6, 6};

Массивті айналып өткеннен кейін Set-те келесі мәндерге ие боламыз.

Орнату: {2,3,4,5,6}, өйткені ол қайталанатын элементтерді жояды

Count = 1, currentElement = arr [0] -1 = 4;

  • Set мәнінде currentElement (4) болған кезде,

Count = count + 1 => count = 2, currentElement– => currentElement = 3

  • Set мәнінде currentElement (3) болған кезде,

Count = count + 1 => count = 3, currentElement– => currentElement = 2

  • Set мәнінде currentElement (2) болған кезде,

Count = count + 1 => count = 4, currentElement– => currentElement = 1

  • Set бар кезінде currentElement (1) жалған, сондықтан ол циклден шығады.

CurrentElement [0] = arr [0] +1 => currentElement = 6 орнатыңыз

  • Set мәнінде currentElement (6) болған кезде,

Count = count + 1 => count = 5, currentElement ++ => currentElement = 7

  • Set бар кезінде currentElement (7) жалған, сондықтан ол циклден шығады

Ол санаудың жиынтық өлшеміне тең екендігін және шарттың орындалуын тексереді, сонда ол шындыққа айналады және негізгі функцияда иә басылады.

Іске асыру

Жиымға рұқсат етілген қайталанатын бүтін сандар бар-жоғын тексеру үшін 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.

Массив рұқсат етілген қайталанатын бүтін сандарды қамтитындығын тексеретін Java коды

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.

Күрделілікті талдау

Уақыттың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.