Најдужа подреза која броји 1с више од броја 0с


Ниво тешкоће Лако
Често питани у Аццентуре амазонка ДЕ Схав самсунг
Ред Хасх

Дали смо поредак целих бројева. Низ садржи само јединице 1 и 0. Изјава о проблему тражи да се сазна дужина најдужег под-низа који има цифру од 1 само је један више од броја 0 у под-низу.

Пример

Улаз:

арр [] = {1,0,1,1,0,0,0}

Излаз:

5

objašnjenje:

Од индекса 0 до 4, {1, 0, 1, 1, 0}, постоје три 1 и два 0. Само још један број 1 од 0.

Улаз:

арр [] = {1,0,1,0,0}

Излаз:

3

objašnjenje:

Од индекса 0 до 2, {1, 0, 1}, постоје две јединице и једна јединица 1. Само још један број 0 од 1.

Алгоритам

  1. Прогласите мапу.
  2. Збир и оутпутЛенгтх поставите на 0.
  3. Пређите низ, док је и = 0 до и <н.
    1. Проверите да ли је арр [и] једнако 0 ако је тачно, додајте -1 суми.
    2. Иначе додајте +1 суми.
    3. Проверите да ли је збир је једнак на 1, а затим повећајте вредност оутпутЛенгтх за 1.
    4. У супротном, проверите да ли карта садржи зброј ако је тачно, а затим на зброј додајте збир и тренутну вредност и на мапу.
    5. Проверите да ли карта садржи (сум-1).
    6. Ако је оутпутЛенгтх мањи од и-индекса (вредност збира на мапи).
      1. Ако је тачно, ажурирајте оутпутЛенгтх на и-индек.
  4. Повратна дужина излаза.

Објашњење

Прогласићемо а Мапа. На тој мапи ћемо сачувати вредност збира и тренутну вредност индекса, ако услов задовољава. Узмимо две променљиве и поставимо сум на 0, а оутпутЛенгтх на 0. Током проласка низом одабрат ћемо сваки елемент низа и проверити да ли је арр [и] једнак 0, ако се утврди да је једнак, додаћемо -1 за сабирање и складиштење у зброј, у супротном, ако нисмо утврдили да је 0, додаћемо позитивно 1 за збрајање и сачувати за зброј.

Разлог за то негативно 1 и позитивно 1 је што се претварамо да су све 0 на -1 и додајемо их са 1, тако да ћемо увек добити 0. Али проверићемо да ли је зброј позитиван 1, што указује на то да ћемо имати један вишак 1, а затим број 0.

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

Имплементација

Ц ++ програм за најдужу подреду која броји 1 с више од броја 0

#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

Јава програм за најдужи подниз који броји 1 с Један више од 0 с

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

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

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

Он) где „Н“  је број елемената у низу.

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

Он) где „Н“  је број елемената у низу.