Bitişik elementləri olan ən böyük alt dizinin uzunluğu

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon Bloomberg Cisco Karat Monotip həllər Paytm PayU İctimai Sapient SAP Laboratoriyaları
Geyim SükutBaxılıb 45

"Bitişik elementləri olan ən böyük alt dizinin uzunluğu" problemi sizə verildiyini bildirir tam array. Problem ifadəsi, elementlərin ardıcıllıqla (davamlı, ya artan, ya da enən) yerləşə biləcəyi ən uzun bitişik alt massivin uzunluğunu öyrənməyi xahiş edir. Dizidəki rəqəmlər bir neçə dəfə baş verə bilər.

misal

Bitişik elementləri olan ən böyük alt dizinin uzunluğuPin

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

Izahat

0-ci indeksdən 3-cü indeksə qədər olan rəqəm, 10, 12, 13, 11 rəqəmlərini ehtiva edir, bunların uzunluğu 10-ə çevrilən 11, 12, 13, 4 şəklində yerləşdirilə bilər.

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

Izahat

1-ci indeksdən 3-cü indeksə qədər olan rəqəm 1, 3, 2 rəqəmlərini ehtiva edir, bunların uzunluğu 1-ə bərabər olan 2, 3, 3-də düzəldilə bilər.

Alqoritm

  1. Set maksimum uzunluq 1 üçün.
  2. Bir döngə açın, i = 0, i <l -1,
    1. Bəyan edin a Set və dəstə arr [i] əlavə edin.
    2. Dəyərini təyin edin maxlenminlen arr [i].
    3. J = l + 1-dən başlayaraq j <l,
      1. Dəstin arr [j] dəyərinə sahib olub olmadığını yoxlayın,
        1. Doğrudursa, pozun.
        2. Başqa,
          1. Arr [j] -i Set-ə əlavə edin.
          2. Minlen və arr [j] arasındakı minimumu tapın və minlenə qədər saxlayın.
          3. Maxlen və arr [j] arasındakı maksimumu tapın və maxlenə qədər saxlayın.
          4. Maxlen-min = = j - i olub olmadığını yoxlayın
            1. Əgər doğrudursa, maxLength və max-minlen +1 arasındakı maksimumu tapın və maxLength-ə qədər saxlayın.
  3. MaxLength qayıt.

Izahat

Ardıcıllıqla düzəldilə bilən bəzi nömrələrə sahib olan ən uzun bitişik alt dizinin uzunluğunu öyrənməyi xahiş edən bir sual verilir. Verilən massivin təkrarlanan nömrələrə sahib olması halları ola bilər. Bu işi də həll etməliyik. Çözüm əldə etmək üçün a Set və təkrarlanan elementlərə baxacaq bir iç içə döngə.

Bir nümunəni nəzərdən keçirək:

misal

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

Bir döngə açdıqdan sonra bir Dəstdən istifadə edəcəyik və sayını bir-bir əlavə edib maxlen və minlen dəyərini arr [i] olaraq təyin edəcəyik. Sonra mövcud elementi qabaqda bir elementdən başlayaraq iç içə döngəni açın, çünki indiki elementi Set-ə daxil etmişik. Dəstin arr [j] dəyərini ehtiva etdiyini yoxlayın, element tapılıbsa qırın. Başqa arr [j] dəyərini Set-ə daxil edin və maxlen və arr [j] arasındakı maksimumu, minlen və arr [j] arasındakı minimumu tapın və müvafiq olaraq maxlen və minlen-ə kimi saxlayın. Maxlen-min-in ji ilə bərabər olub olmadığını yoxlayın, sonra maxLength dəyərini yeniləyin.

maxLength = 1.

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

j = i + 1 = 1, əgər mySet 12-yə bərabər olacaqsa,

Beləliklə, 12-ni mySet-ə daxil edin və maksimum 12 və 10-u, minimumu tapın və 12-ni maxlenə, 10-u minlenə yığın və maxlen-minlenin j - i-yə bərabər olub olmadığını yoxlayın, lakin yalandır.

j = 2, mySet 13-ə sahib olarsa, yalnışdır,

Beləliklə, 13-ü mySet-ə daxil edin və maksimum 13 və 12-ni tapın və 13-ü maxlenə, 10-u minlenə yığın və maxlen-minlenin j - i-yə bərabər olub olmadığını yoxlayın.

j = 3, mySet 11-ə sahib olarsa, yalnışdır,

Beləliklə, 11-i mySet-ə daxil edin və maksimum 11 və 10-u tapın və 13-ü maxlenə, 10-u minlenə yığın və maxlen-minlen-in j - i-ə bərabər olub olmadığını yoxlayın, çünki indi 13-10 3-0-a bərabərdir. Beləliklə, maxLength və maxlen-minlen + 1 max (1, 13-10 + 1) maksimumunu taparaq maxLength-i yeniləyin və 4-ün olduğu və 4-in maxLength-də saxlanıldığını və dizini keçərək davam edəcəyini və bitişik alt dizidən daha uzun uzunluğu tapana qədər qoyun.

Çıxış: 4

Kodu

Bitişik elementləri olan ən böyük alt dizinin uzunluğunu tapmaq üçün C ++ kodu

#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

Bitişik elementləri olan ən böyük alt dizinin uzunluğunu tapmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n)2) hara "N" massivdəki elementlərin sayıdır.

Kosmik Mürəkkəblik

O (n) hara "N" massivdəki elementlərin sayıdır.

Translate »