Дарозии калонтарин зерсохтор бо элементҳои ҳамҷоя  


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Adobe Amazon Блумберг Cisco Карат Solutions Monotype Пардохт PayU Publicis Sapient Лабораторияҳои SAP
тартиботи ҳарбӣ Хаш

Масъалаи "Дарозии зерзарбаи калонтарин бо унсурҳои ҳамҷоя" изҳор медорад, ки ба шумо ан ҳамаҷониба асал. Дар гузориши масъала хоҳиш карда мешавад, ки дарозии зер массиви дарозтарини ҳамсояро фаҳмед, ки элементҳои он бо пайдарҳамӣ ҷойгир карда шаванд (доимӣ, ё афзоиш ё камшаванда). Рақамҳои массив метавонанд якчанд маротиба рӯй диҳанд.

мисол  

Дарозии калонтарин зерсохтор бо элементҳои ҳамҷоя

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. Эълом кунед a маҷмӯи ва arr [i] -ро ба Маҷмӯа илова кунед.
    2. Арзиши макслен ва минлен ба arr [i].
    3. Доираро аз j = i + 1 сар кунед, дар ҳоле ки j <l,
      1. Санҷед, ки Set арзиши arr [j] дорад,
        1. Агар рост бошад, мешиканед.
        2. Дигар,
          1. Arr [j] -ро ба Set илова кунед.
          2. Ҳадди ақали байни minlen ва arr [j] -ро пайдо кунед ва онро то minlen нигоҳ доред.
          3. Максимумро байни maxlen ва arr [j] муайян кунед ва онро то maxlen нигоҳ доред.
          4. Санҷед, ки оё maxlen-min = = j - i
            1. Агар рост бошад, пас ҳадди аксарро байни maxLength ва max-minlen +1 дарёфт кунед ва то maxLength нигоҳ доред.
  3. Бозгаштан maxLength.
ҳамчунин нигаред
Чоргоникҳоро аз чор массиви ҷудошуда ҳисоб кунед, ки ҷамъашон ба арзиши додашудаи х баробар аст

Шарҳ

Ба мо саволе дода мешавад, ки дарёбии дарозии зерсатри массиви дарозтаринро, ки дорои баъзе ададҳо мебошад, ки онҳоро дар пайдарпаӣ ҷобаҷо кардан мумкин аст. Ҳолате вуҷуд дошта метавонад, ки массиви додашуда рақамҳои такрорӣ дошта бошад. Мо бояд он парвандаро ҳам баррасӣ кунем. Барои ба даст овардани ҳалли масъала, мо истифода мебарем маҷмӯи ва ҳалқаи лона, ки дар бораи унсурҳои такрорӣ ғамхорӣ мекунанд.

Биёед як мисолро дида бароем:

мисол

Арр [] = {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 дошта бошад, бардурӯғ,

Пас, ба mySet 13-ро дохил кунед ва ҳадди аксар 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 - i баробар аст, ҳоло дуруст аст, зеро 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) ки дар "Н" шумораи унсурҳои массив аст.

ҳамчунин нигаред
Вақте ки элементҳо бо диапазон маҳдуд намешаванд, дар массиви додашуда такрори онро ёбед

Мураккабии фазо

Эй (н) ки дар "Н" шумораи унсурҳои массив аст.