Даўжыня самага вялікага падмасіва з сумежнымі элементамі  


Узровень складанасці серада
Часта пытаюцца ў Саман амазонка Bloomberg Cisco Karat Рашэнні для манатыпіі Paytm PayU Publicis Sapient Лабараторыі SAP
масіў гашыш

У задачы "Даўжыня найбольшага падмасіва з сумежнымі элементамі" гаворыцца, што вам дадзена цэлае масіў. Пастаноўка задачы патрабуе высветліць даўжыню самага доўгага сумежнага падмасіва, элементы якога могуць быць размешчаны ў паслядоўнасці (бесперапыннай, альбо ўзрастаючай, альбо сыходнай). Лічбы ў масіве могуць паўтарацца некалькі разоў.

Прыклад  

Даўжыня самага вялікага падмасіва з сумежнымі элементаміPin

arr[] = {10, 12, 13, 11, 8, 10, 11, 10}
4

Тлумачэнне

Лік, пачынаючы з 0-га індэкса да 3-га індэкса, утрымлівае лічбы 10, 12, 13, 11, якія можна размясціць такім чынам, 10, 11, 12, 13, даўжыня якіх становіцца 4.

arr[] = {1, 1, 3, 2, 8, 4, 8, 10}
3

Тлумачэнне

Лік, пачынаючы з 1-га індэкса да 3-га індэкса, утрымлівае лічбы 1, 3, 2, якія можна размясціць такім чынам, 1, 2, 3, даўжыня якіх роўная 3.

Алгарытм  

  1. Усталёўка maxLength да 1.
  2. Адкрыйце цыкл, i = 0, а i <l -1,
    1. Абвясціце а Усталёўка і дадайце arr [i] у набор.
    2. Усталюйце значэнне макслен і мінлен абгрунтаваць [i].
    3. Адкрыйце цыкл, пачынаючы з j = i + 1, а j <l,
      1. Праверце, ці ёсць у Set значэнне arr [j],
        1. Калі дакладна, перапынак.
        2. Інакш,
          1. Дадайце arr [j] у набор.
          2. Даведайцеся мінімум паміж minlen і arr [j] і захавайце яго ў minlen.
          3. Даведайцеся максімум паміж maxlen і arr [j] і захавайце яго ў maxlen.
          4. Праверце, калі maxlen-min = = j - i
            1. Калі дакладна, то высветліце максімум паміж maxLength і max-minlen +1 і захавайце яго ў maxLength.
  3. Вяртанне maxLength.
Глядзіце таксама
Падлічыце ў чатыры разы з чатырох адсартаваных масіваў, сума якіх роўная зададзенаму значэнню х

Тлумачэнне

Нам задаюць пытанне, які патрабуе высветліць даўжыню самага доўгага сумежнага падмасіва, які мае некалькі нумароў, якія можна размясціць у паслядоўнасці. Можа быць так, што дадзены масіў мае паўтаральныя нумары. Мы павінны разгледзець і гэтую справу. Каб атрымаць рашэнне, мы будзем выкарыстоўваць Усталёўка і ўкладзены цыкл, які будзе клапаціцца пра дублікаты элементаў.

Давайце разгледзім прыклад:

Прыклад

Arr [] = {10, 12, 13, 11, 8, 10}

Мы будзем выкарыстоўваць Set пасля адкрыцця цыкла і дадаць нумар па адным, і ўсталюем значэнне maxlen і minlen у arr [i]. Затым адкрыйце ўкладзены цыкл, пачынаючы з аднаго элемента перад бягучым элементам, таму што мы ўжо ўставілі бягучы элемент у Set. Праверце, ці ўтрымлівае Set значэнне arr [j], калі элемент знойдзены, то зламайце. У іншым выпадку ўстаўце значэнне arr [j] у Set і даведайцеся максімум паміж maxlen і arr [j], а таксама мінімум паміж minlen і arr [j] і захавайце яго ў maxlen і minlen адпаведна. Праверце, калі maxlen-min роўна ji, затым абнавіце значэнне maxLength.

maxLength = 1.

i = 0, mySet = {10}, minlen = 10, maxlen = 10

j = i + 1 = 1, калі ў mySet будзе 12, гэта ілжыва,

Так што ўстаўце 12 у mySet і знайдзіце максімум 12 і 10 і мінімум і захавайце 12 у maxlen і 10 у minlen і праверце, ці роўны maxlen-minlen j - i, але гэта ілжыва.

j = 2, калі ў mySet будзе 13, гэта ілжыва,

Такім чынам, устаўце 13 у mySet і знайдзіце максімум 13 і 12 і захавайце 13 у maxlen і 10 у minlen і праверце, ці роўны maxlen-minlen j - i ілжывы.

Глядзіце таксама
Найменшы элемент паўтарыўся роўна K Times

j = 3, калі ў mySet будзе 11, гэта ілжыва,

Такім чынам, устаўце 11 у mySet і знайдзіце максімум 11 і 10 і захавайце 13 у maxlen і 10 у minlen і праверце, ці роўны maxlen-minlen j - я праўда, таму што 13-10 роўна 3-0. Такім чынам, абнавіце maxLength, высветліўшы максімум maxLength і maxlen-minlen + 1 max (1, 13-10 + 1), і апынецца, што 4 і 4 захоўваюцца ў maxLength, і ён будзе працягваць перамяшчаць масіў і усталёўваецца, пакуль ён не знойдзе даўжыню большую, чым даўжыня сумежнага падмасіва.

Выхад: 4

код  

Код C ++ для пошуку даўжыні самага вялікага падмасіва з сумежнымі элементамі

#include<set>
#include<iostream>

using namespace std;

int getLongestLength(int arr[], int l)
{
    int maxLength = 1;
    for (int i=0; i<l-1; i++)
    {
        set<int> mySet;
        mySet.insert(arr[i]);
        int minlen = arr[i], maxlen = arr[i];

        for (int j=i+1; j<l; j++)
        {
            if (mySet.find(arr[j]) != mySet.end())
                break;

            mySet.insert(arr[j]);
            minlen = min(minlen, arr[j]);
            maxlen = max(maxlen, arr[j]);

            if (maxlen - minlen == j - i)
                maxLength = max(maxLength, maxlen - minlen + 1);
        }
    }
    return maxLength;
}
int main ()
{
    int arr[] = {10, 12, 13, 11, 8, 10};
    int l = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the Longest contiguous Sub-Array is: " << getLongestLength(arr, l);
    return 0;
}
Length of the Longest contiguous Sub-Array is: 4

Код Java, каб знайсці даўжыню самага вялікага падмасіва з сумежнымі элементамі

import java.util.HashSet;

class largestSubArrayContiguousElements
{
    public static int getLongestLength(int arr[])
    {
        int l = arr.length;
        int maxLength = 1;

        for (int i=0; i< l-1; i++)
        {
            HashSet<Integer> mySet = new HashSet<>();
            mySet.add(arr[i]);

            int min = arr[i];

            int max = arr[i];

            for (int j=i+1; j<l; j++)
            {
                if (mySet.contains(arr[j]))
                    break;

                mySet.add(arr[j]);
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);

                if (max-min == j-i)
                    maxLength = Math.max(maxLength, max-min+1);
            }
        }
        return maxLength;
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 12, 13, 11, 8, 10};
        System.out.println("Length of the Longest contiguous SubArray is: "+getLongestLength(arr));
    }
}
Length of the Longest contiguous SubArray is: 4

Аналіз складанасці  

Складанасць часу

О (н2) дзе "П" - колькасць элементаў у масіве.

Глядзіце таксама
Знайсці дублікаты ў дадзеным масіве, калі элементы не абмежаваныя дыяпазонам

Касмічная складанасць

Аб (п) дзе "П" - колькасць элементаў у масіве.