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


Рівень складності Легко
Часто запитують у Аколіт саман Амазонка Фуркіти MAQ
масив Мішанина

Постановка проблеми  

Припустимо, у вас є масив цілих чисел розміру 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. Тому що пізніше ми також будемо перевіряти послідовні числа. Ми знову обходимо масив, вибираючи кожен елемент і перевіряючи, чи є карта має значення arr [i], якщо true, тоді ми збираємося вибрати цей елемент у тимчасову змінну і перевірити, що якщо карта містить цю temp, якщо true, то збільшимо значення temp на 1, а потім перевіримо ще раз знову збільште його, продовжуйте це, поки на карті не буде цього збільшеного значення. Тепер, коли ми виходимо з цього циклу, ми отримаємо найбільш збільшене значення поточного елемента масиву, яке присутнє на карті, а також збільшуємо його на рахунок 1, тому це також будуть послідовні числа.

Тепер нам доведеться з’ясувати максимум виходу та різницю temp-arr [i], не думайте, ніби ця різниця дає неправильне число підрахунку, оскільки ми отримаємо збільшене значення temp під час виходу з циклу, ми отримаємо правильний підрахунок послідовних чисел. Потім ми збережемо максимум між вихідним та різницею temp-arr [i] (output, temp-arr [i]). Arr [i] - це лише початкова точка для ряду послідовних чисел і тимчасова, кінцева точка. Ці кроки будуть повторюватися доти, доки ми не знайдемо максимальний результат після обходу всього масиву.

Максимальна кількість послідовних чисел, представлених у масивіPin

Реалізація  

Програма 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

Аналіз складності для пошуку максимальних послідовних чисел, представлених у масиві  

Складність часу

О (п) де "N" - кількість елементів у масиві. Оскільки ми використовували HashSet, який дозволяє операцію вставки, видалення та пошуку за постійний час.

Дивись також
Замініть два послідовних рівні значення на одне більше

Складність простору

О (п) де "N" - кількість елементів у масиві. Ми зберегли N елементів у множині, таким чином, лінійна просторова складність.

Посилання