Μήκος του μεγαλύτερου υπόγειου με γειτονικά στοιχεία


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις πλίθα αμαζόνα Bloomberg Cisco καράτιο Μονοτυπικές Λύσεις Paytm PayU Publicis Sapient SAP Labs
Παράταξη Χασίσι

Το πρόβλημα "Μήκος του μεγαλύτερου υποστρώματος με συνεχόμενα στοιχεία" δηλώνει ότι σας δίνεται ένα ακέραιος αριθμός παράταξη. Η δήλωση προβλήματος ζητά να ανακαλύψει το μήκος του μακρύτερου συνεχόμενου υποσυστήματος του οποίου τα στοιχεία μπορούν να τακτοποιηθούν σε μια ακολουθία (συνεχής, είτε αύξουσα είτε φθίνουσα). Οι αριθμοί στον πίνακα μπορούν να εμφανιστούν πολλές φορές.

Παράδειγμα

Μήκος του μεγαλύτερου υπόγειου με γειτονικά στοιχεία

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. σετ μέγιστο μήκος να 1.
  2. Άνοιγμα βρόχου, i = 0, ενώ i <l -1,
    1. Δήλωση α σετ και προσθέστε arr [i] στο σύνολο.
    2. Ορίστε την τιμή του maxlen λεπτό στο arr [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}

Θα χρησιμοποιήσουμε ένα σετ μετά το άνοιγμα ενός βρόχου και θα προσθέσουμε τον αριθμό, έναν κάθε φορά, και θα ορίσουμε την τιμή των maxlen και minlen σε arr [i]. Στη συνέχεια, ανοίξτε ένα ένθετο βρόχο ξεκινώντας από ένα στοιχείο μπροστά από το τρέχον στοιχείο, επειδή έχουμε ήδη εισαγάγει το τρέχον στοιχείο στο σύνολο. Ελέγξτε αν το Σετ περιέχει την τιμή του 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 είναι ψευδές.

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) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

Διαστημική πολυπλοκότητα

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.