Проверите да ли низ садржи суседне целине са дозвољеним дупликатима


Ниво тешкоће Средњи
Често питани у Аццентуре амазонка Дирецти фацебоок Интуит
Ред Хасх низ

Добија се поредак целих бројева који могу садржати и дупликате елемената. Изјава о проблему тражи да се открије да ли је скуп суседних целих бројева, испишите „Да“ ако јесте, одштампајте „Не“ ако није.

Пример

Узорак уноса:

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

Узорак излаза:

да

objašnjenje:

Има скуп суседних целих бројева броја [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 и наставићемо да је повећавамо у каснијим операцијама. Провериће величину суседног скупа целих бројева јер ће имати величину различиту од Сет ако у низу не постоје суседни цели бројеви. Арр [0] -1 би била вредност цуррентЕлемент. Припазиће на скуп интегерс.

Отворите петљу и она ће наставити док Сет не садржи цуррентЕлемент, јер ћемо у петљи повећати вредност цоунт за 1 (цоунт = цоунт + 1) и смањити вредност цуррентЕлемент за 1 (цуррентЕлемент = цуррентЕлемент - 1). Подесите вредност цуррентЕлемент на арр [0] +1 и отворите другу петљу и она ће такође наставити док Сет не садржи цуррентЕлемент у себи, али овог пута повећаћемо обе вредности за 1 цоунт ++ и цуррентЕлемент ++. Напокон ћемо проверити да ли је вредност цоунт једнака величини Сет-а, ако се утврди да је тачно, онда труе труе иначе ретурн фалсе.

Размотримо пример:

Пример

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

Након преласка низа, у Сету ћемо имати следеће вредности.

Сет: {2,3,4,5,6}, јер уклања дуплиране елементе

Цоунт = 1, цуррентЕлемент = арр [0] -1 = 4;

  • Иако Сет има цуррентЕлемент (4) је тачно,

Цоунт = цоунт + 1 => цоунт = 2, цуррентЕлемент– => цуррентЕлемент = 3

  • Иако Сет има цуррентЕлемент (3) је тачно,

Цоунт = цоунт + 1 => цоунт = 3, цуррентЕлемент– => цуррентЕлемент = 2

  • Иако Сет има цуррентЕлемент (2) је тачно,

Цоунт = цоунт + 1 => цоунт = 4, цуррентЕлемент– => цуррентЕлемент = 1

  • Иако Сет има цуррентЕлемент (1) је фалсе, па излази из петље.

Подесите цуррентЕлемент [0] = арр [0] +1 => цуррентЕлемент = 6

  • Иако Сет има цуррентЕлемент (6) је тачно,

Цоунт = цоунт + 1 => цоунт = 5, цуррентЕлемент ++ => цуррентЕлемент = 7

  • Иако Сет има цуррентЕлемент (7) је фалсе, па излази из петље

Провериће да ли је бројање једнако величини скупа и да ли услов задовољава, па ће се вратити тачно и у главној функцији ће бити исписано да

Имплементација

Ц ++ код за проверу да ли низ садржи суседне целобројне бројеве са дозвољеним дупликатима

#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.

Анализа сложености

Сложеност времена

Он) где „Н“ је број елемената у низу.

Сложеност простора

Он) где „Н“ је број елемената у низу.