Најголема под-низа со еднаков број 0 и 1s


Ниво на тешкотија Медиум
Често прашувано во Амазон Coursera GreyOrange MakeMyTrip Морган Стенли Исплата Synopsys Тајмс Интернет
Низа Хаш

Дадена ви е низа цели броеви. Целосните бројки се само 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 и 1s

  1. Прогласи а HashMap.
  2. Намести сума, максимална должина, почетен индекс до 0 и endIndex до -1.
  3. Поминете низ низата и ажурирајте го секој елемент од низата како -1 ако е еднаков на 0.
  4. Започнете јамка од 0 до n-1 (n е должината на низата).
    1. Додадете ја секоја вредност на arr [i] на збирот.
    2. Проверете дали збирот е еднаков на 0, ако е точно,
      1. Потоа ажурирајте максимална должина како јас + 1, и endIndex како што јас.
    3. Проверете дали мапата содржи збир + n во неа,
      1. Потоа ажурирајте ја должината на maxLength како вредност i - мапа (збир + n) од картата и завршена Индекс како i.
    4. Друго ставете ја таа сума + n на картата.
  5. Печати endingIndex - maxLength + 1 и endingIndex.

Објаснување

Со оглед на низата и од нас се бара да ја откриеме најголемата под-низа со еднаков број 0 и 1. Пронајдете го опсегот на под-низата така што тој треба да биде најголем меѓу сите должини на сите под-низи што има еднаков број 0 и 1. Ние ќе го користиме HashMap за складирање на број вредности во него. Хашинг обезбедува ефикасен пристап и подобра сложеност во времето. Земете ги вредностите сума, максимална должина како 0, тогаш ќе го ажурираме истовремено во кодот. Haveе имаме една променлива наречена endingIndex, ова ќе ја задржи вредноста на последната точка од опсегот каде што треба да биде максималната должина на опсегот на краевите на под-низата.

Преминете низ низата, за да откриете дали некоја од вредноста на низата е еднаква на 0, тогаш ќе ја обележиме како -1, и ќе ја оставиме вредноста на низата што го држи 1-от во него како што е. Бидејќи тука нема да го дознаеме вистинскиот опсег. Логиката е да се бројат еднакво бр на нули и оние што значат парен опсег на должина. Значи, ние ќе го означиме 0 како -1, и кога ќе ги додадеме вредностите во низата. Ако ја најдеме збирот како 0, тоа значи дека пронајдовме еден пар еднакви и нули, бидејќи секој -1 и 1 прават 0 како збир бидејќи секој 0 го означивме како -1, за да можеме тоа да го броиме.

Goingе ја сумираме секоја вредност во низата и ќе откриеме дали е еднаква на 0, ако е еднаква, ажурирајте ја максималната должина на низата и индексот на крајот на низата. Toе го ставиме збирот + n на картата, ако тоа веќе не постои, и ако постои, проверете некои услови, а потоа ажурирајте ја вредноста на maxLength и endingIndex. Печатење endingIndex - maxLength + 1 како почетна точка на опсегот и endingIndex како крајна точка на опсегот.

Најголема под-низа со еднаков број 0 и 1s

Код

C ++ код за да ја пронајдете најголемата под-низа со еднаков број 0 и 1s

#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 и 1s

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 (n) затоа што користевме HashMap. Бидејќи HashMap може да вметне, избрише или измени елементи во сложеноста на времето О (1).

Комплексноста на просторот

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