Максимални последователни числа, представени в масив


Ниво на трудност Лесно
Често задавани в Аколит Кирпич Амазонка Fourkites Maq
Array Хашиш

Декларация за проблема

Да предположим, че имате масив от числа с размер N. Проблемът „Максимални последователни числа, присъстващи в масив“ иска да открие максималния брой последователни числа, които могат да бъдат разпръснати в масив.

Пример

arr[] = {2, 24, 30, 26, 99, 25}
3

Обяснение: Последователните числа са ⇒ 24, 25, 26 (набор от 3).

arr[] = { -8, 9 , -1, -6, -5}
2

Обяснение: Последователните числа са ⇒ -6, -5 (набор от 2).

алгоритъм

1. Declare a set.
2. Do traversing of the array, and insert all the values of array into the Set.
3. Set output to 0.
4. Traverse the array from i=0, to i<n(length of the array).
  1. Check if Set contains the arr[i].
    1. If true, then pick the current array element and store it to temp.
  2. While Set contains the temp, repeatedly increases the values of temp.
  3. Find out the maximum between output and temp-arr[i] and store it into the output.
5. Return output.

Обяснение

Като се има предвид цяло число масив, трябва да открием най-големия брой последователни числа, присъстващи в масив. Ще използваме a определен. Set осигурява функция за премахване на подобен елемент. Така че, не е нужно да се притесняваме за манипулатора на общия елемент, той ще бъде обработен автоматично.

Ще добавим всички стойности на масива в Set. Защото по-късно ще проверим и последователни числа. Ще прекосим масива отново, избирайки всеки елемент и ще проверим дали карта има този arr [i], ако е вярно, тогава ще изберем този елемент във временна променлива и ще проверим отново, ако картата съдържа тази temp, ако е true, след това увеличаваме стойността на temp с 1, и след това проверяваме отново и отново го увеличете, продължава това, докато картата няма тази увеличена стойност. Сега, когато излезем от този цикъл, ще получим най-увеличената стойност на текущия елемент на масив, който присъства в карта, също така го увеличаваме с броя на 1, така че това също ще бъдат последователни числа.

Сега трябва да разберем максималния изход и разликата в temp-arr [i], не мислете така, сякаш тази разлика дава грешен номер на броя, тъй като ще получим увеличената стойност на temp, докато излизаме от цикъл, ще получим правилния брой на присъстващите последователни числа. След това ще съхраним максимума между изхода и разликата на temp-arr [i] (output, temp-arr [i]). Arr [i] е само начална точка за поредица от последователни числа и темп, крайна точка. Тези стъпки ще се повтарят, докато не намерим максималния изход след като обходим целия масив.

Максимални последователни числа, представени в масив

изпълнение

Програма C ++ за намиране на максимални последователни числа, представени в масив

#include<iostream>
#include<unordered_set>

using namespace std;

int getMaxConsecutiveNumber(int arr[], int n)
{
    unordered_set<int> SET;
    for (int i = 0; i < n; i++)
        SET.insert(arr[i]);

    int output = 0;
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr[i] - 1) == SET.end())
        {
            int temp = arr[i];

            while (SET.find(temp) != SET.end())
                temp++;

            output = max(output, temp - arr[i]);
        }
    }
    return output;
}
int main()
{
    int arr[] = {2, 24, 30, 26, 99, 25 };
    int n = sizeof(arr) / sizeof(int);
    cout << "Largest Set found : "<<getMaxConsecutiveNumber(arr, n)<< endl;
    return 0;
}
Largest Set found : 3

Програма Java за намиране на максимални последователни числа, присъстващи в масив

import java.util.HashSet;

class LargestConsecutiveSet
{
    public static int getMaxConsecutiveNumber(int arr[], int n)
    {
        HashSet<Integer> SET = new HashSet<Integer>();
        for (int i = 0; i < n; i++)
        {
            SET.add(arr[i]);
        }
        int output = 0;
        for (int i = 0; i < n; i++)
        {
            if(SET.contains(arr[i]))
            {
                int temp = arr[i];
                while (SET.contains(temp))
                    temp ++;

                output = Math.max(output, temp - arr[i]);
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {2, 24, 30, 26, 99, 25};
        int n = arr.length;
        System.out.println("Largest Set found : "+getMaxConsecutiveNumber(arr, n));
    }
}
Largest Set found : 3

Анализ на сложността за намиране на максимални последователни числа, представени в масив

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

О (п) където "н" е броят на елементите в масива. Тъй като използвахме HashSet, който позволява вмъкване, изтриване и търсене в постоянно време.

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

О (п) където "н" е броят на елементите в масива. Съхранихме N елемента в множеството, като по този начин линейната сложност на пространството.

препратка