أكبر مصفوفة فرعية بعدد متساوٍ من 0 و 1  


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون Coursera رمادي ميك ماي تريب مورجان ستانلي Paytm سينوبسيس مرات الانترنت
مجموعة مزيج

يتم إعطاؤك مجموعة من الأعداد الصحيحة. الأعداد الصحيحة هي 0 و 1 فقط في مصفوفة الإدخال. يطلب بيان المشكلة معرفة أكبر مصفوفة فرعية يمكن أن يكون لها عدد متساوٍ من 0 و 1.

مثال  

arr[]={0,1,0,1,0,1,1,1}
0 to 5 (total 6 elements)

تفسير

من موضع الصفيف من 0 إلى 5 ، كان هناك صفر و 0 يساوي

0 ثانية 3

1 ثانية ⇒ 3

وهذه أكبر مصفوفة فرعية لا تساوي صفرًا وواحدًا.

خوارزمية للعثور على أكبر مصفوفة فرعية بعدد متساوٍ من 0 و 1  

  1. تعلن أ خريطة التجزئة.
  2. ضبط مجموع, الحد الاقصى للطول, بدء الفهرس إلى 0 و المنتهية إلى 1.
  3. اجتياز المصفوفة وتحديث كل عنصر من عناصر المصفوفة كـ -1 إذا كانت تساوي 0.
  4. حلقة البداية من 0 إلى n-1 (n هي طول المصفوفة).
    1. أضف كل قيمة من arr [i] لتجمعها.
    2. تحقق مما إذا كان المجموع يساوي 0 ، إذا كان صحيحًا ،
      1. ثم قم بالتحديث الحد الاقصى للطول مثل i + 1 و المنتهية كما أنا.
    3. تحقق مما إذا كانت الخريطة تحتوي على مجموع + n فيها ،
      1. ثم قم بتحديث طول maxLength كقيمة i - map (sum + n) من الخريطة و endIndex مثل i.
    4. آخر وضع هذا المبلغ + ن في الخريطة.
  5. طباعة الفهرس - maxLength + 1 and endIndex.
انظر أيضا
اجتياز الشجرة (الطلب المسبق والداخل والأمر البريدي)

تفسير  

بالنظر إلى مصفوفة ومطلوب منا إيجاد أكبر مصفوفة فرعية بعدد متساوٍ من 0 و 1. ابحث عن نطاق المصفوفة الفرعية بحيث يكون الأكبر بين جميع أطوال جميع المصفوفات الفرعية التي تحتوي على عدد متساوٍ من 0 و 1. سنستخدم ملف خريطة التجزئة لتخزين ملفات عدد صحيح القيم فيه. تجزئة يوفر نهجًا فعالًا وتعقيدًا أفضل للوقت. خذ القيم مجموع, الحد الاقصى للطول كـ 0 ، سنقوم بتحديثه في نفس الوقت في الكود. سيكون لدينا متغير واحد يسمى endIndex ، وهذا سيحتفظ بقيمة النقطة الأخيرة من النطاق حيث يجب أن يكون الحد الأقصى لطول نطاق نهايات المصفوفة الفرعية.

اجتياز المصفوفة ، لإيجاد ما إذا كانت أي من قيم المصفوفة تساوي 0 ، سنضع علامة عليها كـ -1 ، ونترك قيمة المصفوفة التي تحمل الرقم 1 فيها كما هي. لأننا هنا لن نكتشف النطاق الفعلي. المنطق هو حساب عدد متساوٍ من الأصفار والآحاد التي تعني نطاقًا متساويًا للطول. لذلك سنضع علامة على 0 كـ -1 ، وعندما نضيف القيم داخل المصفوفة. إذا وجدنا المجموع على أنه 0 ، فهذا يعني أننا وجدنا زوجًا واحدًا من الآحاد والأصفار المتساوية ، لأن كل -1 و 1 يساوي 0 كمجموع لأننا حددنا كل 0 كـ -1 ، لذلك يمكننا حساب ذلك.

سنقوم بتلخيص كل قيمة في المصفوفة ، ومعرفة ما إذا كانت تساوي 0 ، إذا كانت متساوية ، فقم فقط بتحديث الحد الأقصى لطول المصفوفة وفهرس النهاية للمصفوفة. سنضع المجموع + n في الخريطة إذا لم يكن موجودًا بالفعل ، وإذا كان موجودًا ، فتحقق من بعض الشروط ثم قم بتحديث قيمة maxLength و endIndex. طباعة endIndex - maxLength + 1 كنقطة بداية للنطاق و endIndex كنقطة نهاية النطاق.

انظر أيضا
إزالة عناصر القائمة المرتبطة Leetcode Solution

أكبر مصفوفة فرعية بعدد متساوٍ من 0 و 1دبوس

رمز  

كود C ++ للعثور على أكبر مصفوفة فرعية بعدد متساوٍ من 0 و 1

#include<iostream>
#include<unordered_map>

using namespace std;

int getLargestSubA(int arr[], int n)
{
    unordered_map<int, int> MAP;

    int sum = 0;
    int maxLength = 0;
    int endingIndex = -1;

    for (int i = 0; i < n; i++)
        arr[i] = (arr[i] == 0) ? -1 : 1;

    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
        if (sum == 0)
        {
            maxLength = i + 1;
            endingIndex = i;
        }
        if (MAP.find(sum + n) != MAP.end())
        {
            if (maxLength < i - MAP[sum + n])
            {
                maxLength = i - MAP[sum + n];
                endingIndex = i;
            }
        }
        else
            MAP[sum + n] = i;
    }
    cout<<endingIndex - maxLength + 1 <<" to " <<endingIndex;

    return maxLength;
}

int main()
{
    int arr[] = { 0,1,0,1,0,1,1,1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    getLargestSubA(arr, n);
    return 0;
}
0 to 5

التنفيذ في Java للعثور على أكبر مصفوفة فرعية بعدد متساوٍ من 0 و 1

import java.util.HashMap;

class LargestSubArrayWithEqual01
{
    public static int getLargestSubA(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int sum = 0;

        int maxLength = 0;
        int endingIndex = -1;

        for (int i = 0; i < n; i++)
        {
            arr[i] = (arr[i] == 0) ? -1 : 1;
        }

        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
            if (sum == 0)
            {
                maxLength = i + 1;
                endingIndex = i;
            }
            if (MAP.containsKey(sum + n))
            {
                if (maxLength < i - MAP.get(sum + n))
                {
                    maxLength = i - MAP.get(sum + n);
                    endingIndex = i;
                }
            }
            else
                MAP.put(sum + n, i);

        }
        int end = endingIndex - maxLength + 1;
        System.out.println(end + " to " + endingIndex);

        return maxLength;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {0,1,0,1,0,1,1,1};
        int n = arr.length;

        getLargestSubA(arr, n);
    }
}
0 to 5

تحليل التعقيد  

تعقيد الوقت

O (ن) أين "ن" هو عدد العناصر في المصفوفة. هنا يمكننا حل هذه المشكلة في O (n) لأننا استخدمنا HashMap. لأن HashMap يمكنه إدراج العناصر أو حذفها أو تعديلها في تعقيد الوقت O (1).

انظر أيضا
اكتشف ما إذا كانت المصفوفة مجموعة فرعية من مصفوفة أخرى

تعقيد الفضاء

O (ن) أين "ن" هو عدد العناصر في المصفوفة. نظرًا لأن عدد العناصر التي سيتم إدراجها في أسوأ الحالات في التجزئة سيكون n على الأكثر. يتحقق هذا التعقيد المكاني الخطي.