طول أكبر مصفوفة فرعية مع عناصر متجاورة


مستوى الصعوبة متوسط
كثيرا ما يطلب في أدوبي أمازون بلومبرغ سيسكو قيراط حلول مونوتايب Paytm PayU Publicis Sapient مختبرات SAP
مجموعة مزيج

تنص مشكلة "طول أكبر مصفوفة فرعية مع عناصر متجاورة" على أنه تم إعطاؤك قيمة عدد صحيح مجموعة. يطلب بيان المشكلة معرفة طول أطول مصفوفة فرعية متجاورة يمكن ترتيب العناصر في تسلسل (مستمر ، إما تصاعدي أو تنازلي). يمكن أن تحدث الأرقام في المصفوفة عدة مرات.

مثال

طول أكبر مصفوفة فرعية مع عناصر متجاورة

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

تفسير

الرقم الذي يبدأ من الفهرس 0 إلى الفهرس الثالث يحتوي على الأرقام 3 ، 10 ، 12 ، 13 والتي يمكن ترتيبها بطريقة 11 ، 10 ، 11 ، 12 والتي يصبح طولها 13.

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

تفسير

الرقم الذي يبدأ من الفهرس الأول إلى الفهرس الثالث يحتوي على الأرقام 1 ، 3 ، 1 والتي يمكن ترتيبها بطريقة 3 ، 2 ، 1 والتي يصبح طولها 2.

خوارزمية

  1. ضبط الحد الاقصى للطول ل1.
  2. افتح حلقة ، أنا = 0 ، بينما أنا <ل -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.

تفسير

لدينا سؤال يطلب معرفة طول أطول مصفوفة فرعية متجاورة تحتوي على بعض الأرقام التي يمكن ترتيبها في تسلسل. يمكن أن تكون هناك حالة أن المصفوفة المعينة بها أرقام مكررة. نحن بحاجة للتعامل مع هذه القضية أيضًا. للحصول على الحل ، سنستخدم ملف ضبط وحلقة متداخلة تهتم بالعناصر المكررة.

دعنا نأخذ مثالا:

مثال

الوصول [] = {10 ، 12 ، 13 ، 11 ، 8 ، 10}

سنستخدم مجموعة بعد فتح حلقة ونضيف الرقم ، واحدًا تلو الآخر ، ونضبط قيمة maxlen و minlen على arr [i]. ثم افتح حلقة متداخلة تبدأ من عنصر واحد قبل العنصر الحالي ، لأننا أدخلنا العنصر الحالي بالفعل في المجموعة. تحقق مما إذا كانت المجموعة تحتوي على قيمة arr [j] ، إذا تم العثور على عنصر ، فكسر. عدا ذلك ، أدخل قيمة arr [j] في المجموعة واكتشف الحد الأقصى بين maxlen و arr [j] ، وكذلك الحد الأدنى بين minlen و arr [j] وقم بتخزينه في maxlen و minlen على التوالي. تحقق مما إذا كان maxlen-min يساوي ji ، ثم حدِّث قيمة maxLength.

maxLength = 1.

أنا = 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 - 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 (ن) أين "ن" هو عدد العناصر في الصفيف.