Највећи подред са једнаким бројем 0 и 1


Ниво тешкоће Средњи
Често питани у амазонка Цоурсера ГреиОранге МакеМиТрип Морган Стенли Паитм Синопсис Тимес Интернет
Ред Хасх

Добија се низ целих бројева. Цели бројеви су само 0 и 1 у улазном низу. Изјава о проблему тражи да се пронађе највећи под-низ који може имати једнак број 0 и 1.

Пример

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

Објашњење

Са положаја низа 0 до 5 било је једнако 0 и 1

0с цоунт 3

1с цоунт ⇒ 3

А ово је највећи под-низ који има једнаке 0 и 1.

Алгоритам за проналажење највећег низа са једнаким бројем 0 и 1

  1. Изјавите а ХасхМап.
  2. Сет збир, максимална дужина, стартИндек до 0. и ЕНДИндек до -1.
  3. Пређите низом и ажурирајте сваки елемент низа као -1 ако је једнак 0.
  4. Стартна петља од 0 до н-1 (н је дужина низа).
    1. Додајте сваку вредност арр [и] у збир.
    2. Проверите да ли је збир једнак 0, ако је тачно,
      1. Затим ажурирајте максимална дужина као и + 1, и ЕНДИндек као што сам.
    3. Проверите да ли карта садржи збир + н,
      1. Затим ажурирајте дужину макЛенгтх као вредности и - мап (сум + н) са мапе и ЕНДИндек као и.
    4. Иначе је тај збир + н ставио на мапу.
  5. Штампање ЕНДИндек - макЛенгтх + 1 и ЕНДИндек.

Објашњење

С обзиром на низ и од нас се тражи да откријемо највећи под-низ са једнаким бројем 0 и 1. Пронађите опсег под-низа тако да буде највећи међу свим дужинама свих под-низова који садржи једнак број 0 и 1. Користићемо ХасхМап за чување цео број вредности у њему. Хасхинг пружа ефикасан приступ и бољу временску сложеност. Узми вредности збир, максимална дужина као 0 тада ћемо га истовремено ажурирати у коду. Имаћемо једну променљиву која се зове ендИндек, у њој ће се налазити вредност последње тачке опсега где треба да буде максимална дужина опсега крајева под-низа.

Пређите низом да бисте пронашли да ли је било која вредност низа једнака 0, тада ћемо га означити као -1 и оставити вредност низа која у њему држи 1 као што јесте. Јер овде нећемо сазнати стварни домет. Логика је да се броје једнаке нуле и оне које значе чак и опсег дужине. Дакле, означићемо 0 као -1 и када додамо вредности у низу. Ако зброј пронађемо као 0, то значи да смо пронашли један пар једнаких и нула, јер сваки -1 и 1 чине 0 као збир, будући да смо сваку 0 означили као -1, па то можемо рачунати.

Идемо да сумирамо сваку вредност у низу и пронађемо да ли је једнака 0, ако је једнака, само ажурирамо макЛенгтх низа и ЕНДИндек низа. Ставићемо суму + н на мапу ако већ не постоји, а ако постоји, онда проверите неке услове, а затим ажурирајте вредност макЛенгтх и ЕНДИндек. Одштампајте ЕНДИндек - макЛенгтх + 1 као почетну тачку опсега и ЕНДИндек као крајњу тачку опсега.

Највећи подред са једнаким бројем 0 и 1

код

Ц ++ код за проналажење највеће подниза са једнаким бројем 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

Имплементација у Јави за проналажење највећег низа са једнаким бројем 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

Анализа сложености

Сложеност времена

Он) где „Н“ је број елемената у низу. Овде можемо да решимо овај проблем у О (н) јер смо користили ХасхМап. Зато што ХасхМап може уметати, брисати или мењати елементе у сложености времена О (1).

Сложеност простора

Он) где „Н“ је број елемената у низу. Будући да ће број елемената који ће бити уметнути у најгорем случају у хешмапу бити највише н. Постигнута је ова линеарна сложеност простора.