უდიდესი ქვეჯგუფის სიგრძე მომიჯნავე ელემენტებით


Რთული ტური საშუალო
ხშირად ეკითხებიან Adobe Amazon Bloomberg Cisco კარატი მონოტიპის გადაწყვეტილებები Paytm პეუ პუბლიკის საპიენტი SAP ლაბორატორიები
Array Hash

პრობლემა "უდიდესი ქვეჯგუფის სიგრძე მომიჯნავე ელემენტებით" აღნიშნავს, რომ თქვენ გეძლევათ მთელი რიცხვი მასივი. პრობლემის დებულება ითხოვს გრძელი მომიჯნავე ქვე-მასივის სიგრძის გარკვევას, რომლის ელემენტების განლაგება შესაძლებელია თანმიმდევრობით (უწყვეტი, ან აღმავალი ან დაღმავალი). მასივში რიცხვები შეიძლება რამდენჯერმე მოხდეს.

მაგალითი

უდიდესი ქვეჯგუფის სიგრძე მომიჯნავე ელემენტებით

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. უცნობია მაქსიმალური სიგრძე to 1.
  2. გახსენით მარყუჟი, i = 0, ხოლო i <l -1,
    1. გამოაცხადეთ ა უცნობია და დაამატე arr [i] კომპლექტში.
    2. დააყენეთ მნიშვნელობა მაქსლინი და minlen arr [i].
    3. გახსენით მარყუჟი, j = i + 1-დან დაწყებული, j = l,
      1. შეამოწმეთ აქვს თუ არა სეტს arr [j] მნიშვნელობა,
        1. თუ სიმართლეა, დაარღვიე.
        2. სხვა,
          1. დაამატე arr [j] Set- ში.
          2. შეიტყვეთ მინიმუმი minlen- სა და arr [j] - ს შორის და შეინახეთ minlen- მდე.
          3. შეიტყვეთ მაქსიმუმი მაქსილსა და arr [j] - ს შორის და შეინახეთ მაქსილენამდე.
          4. შეამოწმეთ არის maxlen-min = = j - i
            1. თუ სიმართლეა, გაიგეთ მაქსიმუმი maxLength და max-minlen +1 შორის და შეინახეთ maxLength- ში.
  3. დააბრუნე maxLength.

განმარტება

ჩვენ გვეძლევა კითხვა, რომელიც ითხოვს გრძელი მომიჯნავე ქვე-მასივის სიგრძის გარკვევას, რომელსაც აქვს რამდენიმე რიცხვი, რომელთა განლაგებაც შესაძლებელია თანმიმდევრობით. შეიძლება არსებობდეს შემთხვევა, რომ მოცემულ მასივს ჰქონდეს დუბლირებული რიცხვები. ჩვენ იმ საქმესაც უნდა გავუმკლავდეთ. გამოსავალის მისაღებად გამოვიყენებთ ა უცნობია და ჩადგმული მარყუჟი, რომელიც იზრუნებს დუბლირებულ ელემენტებზე.

განვიხილოთ მაგალითი:

მაგალითი

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

ჩვენ გამოვიყენებთ Set- ს მარყუჟის გახსნის შემდეგ და დავუმატებთ რიცხვს, თითოეულად და დავაყენებთ maxlen და minlen მნიშვნელობებს ar [i]. შემდეგ გახსენით ჩადებული მარყუჟი, დაწყებული ერთი ელემენტიდან, ვიდრე მიმდინარე ელემენტს, რადგან ჩვენ უკვე ჩავსვით მიმდინარე ელემენტი 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, არასწორია,

ჩადეთ mySet– ში 12 და იპოვნეთ მაქსიმუმი 12 და 10 და მინიმალური და შეინახეთ 12 maxlen– ში და 10 minlen– ში და შეამოწმეთ maxlen-minlen ტოლია j - i, მაგრამ ეს მცდარია.

j = 2, თუ mySet– ს ექნება 13, არასწორია,

ასე რომ ჩადეთ mySet– ში და იპოვნეთ მაქსიმუმი 13 და 13 და შეინახეთ 12 maxlen– ში და 13 minlen– ში და შეამოწმეთ maxlen-minlen ტოლია j - i არის ყალბი.

j = 3, თუ mySet– ს ექნება 11, არასწორია,

ასე რომ ჩადეთ 11 mySet– ში და იპოვნეთ მაქსიმუმი 11 და 10 და შეინახეთ 13 მაქსლენში და 10 მილენში და შეამოწმეთ არის თუ არა 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) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.