Рубрики

Длина наибольшего подмассива с непрерывными элементами | Набор 2

Для данного массива целых чисел найдите длину самого длинного подмассива, который содержит числа, которые могут быть расположены в непрерывной последовательности.

В предыдущем посте мы обсудили решение, которое предполагает, что элементы в данном массиве различны. Здесь мы обсуждаем решение, которое работает, даже если входной массив имеет дубликаты.

Примеры:

Input:  arr[] = {10, 12, 11};
Output: Length of the longest contiguous subarray is 3

Input:  arr[] = {10, 12, 12, 10, 10, 11, 10};
Output: Length of the longest contiguous subarray is 2 

Идея похожа на предыдущий пост. В предыдущем посте мы проверяли, равно ли максимальное значение минус минимальное значение конечному индексу минус начальный индекс или нет. Поскольку дублирующие элементы разрешены, нам также необходимо проверить, содержит ли подмассив дублирующие элементы или нет. Например, массив {12, 14, 12} следует первому свойству, но числа в нем не являются смежными элементами.
Чтобы проверить дубликаты элементов в подмассиве, мы создаем хеш-набор для каждого подмассива, и если мы находим элемент, уже находящийся в хэш-памяти, мы не учитываем текущий подмассив.

Ниже приводится реализация вышеуказанной идеи.

C ++

/ * Программа CPP, чтобы найти длину наибольшего
подмассив, который имеет все смежные элементы * /
#include<bits/stdc++.h>

using namespace std;

  
// Эта функция печатает все отдельные элементы

int findLength(int arr[], int n)

{

    int max_len = 1; // Инициализировать результат

  

    // Один за другим исправляем начальные точки

    for (int i=0; i<n-1; i++)

    {

        // Создать пустой хэш-набор и

        // добавляем в него i-й элемент.

        set<int> myset;

        myset.insert(arr[i]);

  

        // Инициализируем max и min в

        // текущий подмассив

        int mn = arr[i], mx = arr[i];

  

        // Один за другим фиксируем конечные точки

        for (int j=i+1; j<n; j++)

        {

            // Если текущий элемент уже

            // в хэше, тогда этот подмассив

            // не может содержать смежные элементы

            if (myset.find(arr[j]) != myset.end())

                break;

  

            // Остальное добавляем текущий элемент в хеш

            // установить и обновить min, max, если требуется.

            myset.insert(arr[j]);

            mn = min(mn, arr[j]);

            mx = max(mx, arr[j]);

  

            // Мы уже проверили на

            // дублируем, теперь проверяем на другие

            // свойство и обновление max_len

            // если нужно

            if (mx - mn == j - i)

                max_len = max(max_len, mx - mn + 1);

        }

    }

    return max_len; // Возвращаем результат

}

  
// Метод драйвера для проверки вышеуказанного метода

int main ()

{

    int arr[] = {10, 12, 12, 10, 10, 11, 10};

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Length of the longest contiguous"

         << " subarray is " << findLength(arr, n);

}

  
// Эта статья предоставлена Чхави

Джава

/ * Java-программа, чтобы найти длину самого большого подмассива, который имеет

   все смежные элементы * /

import java.util.*;

  

class Main

{

    // Эта функция печатает все отдельные элементы

    static int findLength(int arr[])

    {

        int n = arr.length;

        int max_len = 1; // Инициализировать результат

  

        // Один за другим исправляем начальные точки

        for (int i=0; i<n-1; i++)

        {

            // Создать пустой хэш-набор и добавить i-й элемент

            // к этому.

            HashSet<Integer> set = new HashSet<>();

            set.add(arr[i]);

  

            // Инициализируем max и min в текущем подмассиве

            int mn = arr[i], mx = arr[i];

  

            // Один за другим фиксируем конечные точки

            for (int j=i+1; j<n; j++)

            {

                // Если текущий элемент уже в хэш-наборе, то

                // этот подмассив не может содержать смежные элементы

                if (set.contains(arr[j]))

                    break;

  

                // Иначе добавляем элемент curremt в набор хэшей и обновляем

                // мин, макс, если требуется.

                set.add(arr[j]);

                mn = Math.min(mn, arr[j]);

                mx = Math.max(mx, arr[j]);

  

                // Мы уже проверяли дубликаты, теперь проверяем

                // для другого свойства и, при необходимости, обновляем max_len

                if (mx-mn == j-i)

                    max_len = Math.max(max_len, mx-mn+1);

            }

        }

        return max_len; // Возвращаем результат

    }

  

    // Метод драйвера для проверки вышеуказанного метода

    public static void main (String[] args)

    {

       int arr[] =  {10, 12, 12, 10, 10, 11, 10};

       System.out.println("Length of the longest contiguous subarray is " +

                           findLength(arr));

    }

}

python3

# Python программа для определения длины наибольшего
# подмассив, имеющий все смежные элементы * /

  
# Эта функция печатает все отдельные элементы

def findLenght(arr, n):

    max_len = 1

    for i in range(0,n - 1):

  

        # Создать пустой хэш-набор и

        # добавить элемент

        myset = set()

        myset.add(arr[i])

  

        # Инициализировать макс и мин в

        # текущий подмассив

        mn = arr[i]

        mx = arr[i]

        for j in range(i + 1,n):

  

            # Если текущий элемент уже

            # в хэше, то этот подмассив

            # не может содержать смежные элементы

            if arr[j] in myset:

                break

  

  

            # Иначе добавить текущий элемент в хеш

            # установить и обновить мин, макс, если требуется.

            myset.add(arr[j])

            mn = min(mn, arr[j])

            mx = max(mx, arr[j])

  

            # Мы уже проверили на

            # дубликаты, теперь проверьте другие

            #property and update max_len

            # если нужно

            if mx - mn == j - i:

                max_len = max(max_len, mx - mn + 1)

  

    return max_len # Вернуть результат

  

  
# Код драйвера

  

arr = [10, 12, 12, 10, 10, 11, 10]

n = len(arr)

print("Length of the longest contiguous subarray is",

                                findLenght(arr,n))

  
# Этот код предоставлен Shrikant13

C #

/ * C # программа для определения длины наибольшего
подмассив, который имеет все смежные элементы * /

using System;

using System.Collections.Generic;

  

class GFG {

      

    // Эта функция печатает все отчетливо

    // элементы

    static int findLength(int []arr)

    {

        int n = arr.Length;

        int max_len = 1; // Инициализировать результат

  

        // Один за другим исправляем начальные точки

        for (int i = 0; i < n-1; i++)

        {

              

            // Создать пустой хэш-набор и

            // добавляем в него i-й элемент.

            HashSet<int> set = new HashSet<int>();

            set.Add(arr[i]);

  

            // Инициализировать макс и мин в токе

            // подрешетка

            int mn = arr[i], mx = arr[i];

  

            // Один за другим фиксируем конечные точки

            for (int j = i+1; j < n; j++)

            {

                  

                // Если текущий элемент уже

                // в хэше, тогда этот подмассив

                // не может содержать смежные

                // элементы

                if (set.Contains(arr[j]))

                    break;

  

                // Остальное добавить элемент curremt в

                // хэш установлен и обновляется мин,

                // max, если требуется.

                set.Add(arr[j]);

                mn = Math.Min(mn, arr[j]);

                mx = Math.Max(mx, arr[j]);

  

                // Мы уже проверены на

                // дубликаты, теперь проверяем

                // другое свойство и обновление

                // max_len при необходимости

                if (mx-mn == j-i)

                    max_len = Math.Max(max_len,

                                  mx - mn + 1);

            }

        }

          

        return max_len; // Возвращаем результат

    }

      

    // Функция драйвера

    public static void Main()

    {

        int []arr = {10, 12, 12, 10, 10, 11, 10};

        Console.WriteLine("Length of the longest"

                   + " contiguous subarray is " +

                               findLength(arr));

    }

}

  
// Этот код предоставлен Sam007


Выход:

Length of the longest contiguous subarray is 2

Временная сложность вышеприведенного решения составляет O (n 2 ) в предположении, что операции хеш-набора, такие как add () и contains (), работают за O (1) времени.

Эта статья предоставлена Арджуном . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Длина наибольшего подмассива с непрерывными элементами | Набор 2

0.00 (0%) 0 votes