أطول مجموعة فرعية بها عدد 1s واحد أكثر من عدد 0s  


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

لقد قدمنا مجموعة من الأعداد الصحيحة. تحتوي المصفوفة على 1 و 0 فقط. بيان المشكلة يطلب معرفة طول أطول مصفوفة فرعية والتي تحتوي على عدد رقم 1 يزيد بمقدار واحد فقط عن عدد 0 في مصفوفة فرعية.

مثال  

الإدخال:

arr [] = {1,0,1,1,0,0,0،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

الإخراج:

5

التفسير:

من 0 إلى 4 فهرس ، {1 ، 0 ، 1 ، 1 ، 0} ، هناك ثلاثة 1 واثنين من 0. فقط عدد واحد إضافي من 1 من 0.

الإدخال:

arr [] = {1,0,1,0,0،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

الإخراج:

3

التفسير:

من 0 إلى 2 فهرس ، {1 ، 0 ، 1} ، هناك اثنان من 1 وواحد صفر. فقط عدد واحد إضافي من 0 من 1.

خوارزمية  

  1. إعلان خريطة.
  2. اضبط المجموع وطول الإخراج على 0.
  3. اجتياز المصفوفة ، بينما i = 0 إلى i <n.
    1. تحقق مما إذا كانت قيمة arr [i] تساوي 0 إذا كانت صحيحة ، ثم أضف -1 إلى المجموع.
    2. إضافة +1 للمجموع.
    3. تحقق مما إذا كان المجموع يساوي إلى 1 ، ثم قم بزيادة قيمة outputLength بمقدار 1.
    4. عدا ذلك ، تحقق مما إذا كانت الخريطة لا تحتوي على المجموع إذا كان صحيحًا ، ثم ضع المجموع والقيمة الحالية لـ i على الخريطة جنبًا إلى جنب مع المجموع.
    5. تحقق مما إذا كانت الخريطة تحتوي على (مجموع -1).
    6. إذا كانت قيمة الإخراج أقل من مؤشر i (قيمة المجموع في الخريطة).
      1. إذا كان هذا صحيحًا ، فقم بتحديث outputLength إلى i-index.
  4. طول إخراج العودة.
انظر أيضا
مجموعة ثنائية بعد عمليات تبديل النطاق M

تفسير  

سوف نعلن أ رسم خريطة. في تلك الخريطة ، سنقوم بتخزين قيمة المجموع والقيمة الحالية لمؤشر ، إذا كان الشرط مستوفيا. خذ متغيرين وضبط المجموع على 0 و outputLength إلى 0. أثناء اجتياز المصفوفة ، سنختار كل عنصر في المصفوفة ، ونتحقق مما إذا كانت قيمة arr [i] تساوي 0 ، وإذا وجد أنها متساوية ، فسنضيف -1 لجمعها وتخزينها لجمعها ، وإلا إذا لم نجد 0 ، فسنضيف الموجب 1 لجمعها وتخزينها لمجموعها.

السبب وراء ذلك سالب 1 وموجب 1 هو أننا نتظاهر بأن كل 0 إلى -1 ونجمعها مع 1 ، لذلك سنحصل على 0 دائمًا. لكننا سنتحقق من مجموع موجب 1 ، مما يشير إلى أننا سنحصل على 1 إضافي ثم عدد 0.

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

انظر أيضا
ابحث عن العنصر المكرر

تطبيق  

برنامج C ++ لأطول مصفوفة فرعية بها عدد 1s واحد أكثر من عدد 0s

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}
Length of the longest Sub-Array : 5

برنامج Java لأطول مجموعة فرعية بها عدد 1s واحد أكثر من عدد 0s

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

        for (int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += -1;
            else
                sum += 1;

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}
Length of the longest Sub-Array : 5

تحليل التعقيد لأطول مصفوفة فرعية بها عدد 1s واحد أكثر من عدد 0s  

تعقيد الوقت

O (ن) أين "ن"  هو عدد العناصر في الصفيف.

تعقيد الفضاء

O (ن) أين "ن"  هو عدد العناصر في الصفيف.