Эң узак Subarray саны 1s дан бир 0 дан көп


Кыйынчылык деңгээли жеңил
Көп суралган Accenture Amazon DE Shaw Samsung
согуштук тизме таштанды

Биз берген согуштук тизме бүтүн сандар. Массивде 1 жана 0 гана бар. Маселенин коюлушу, эң узун суб-массивдин узундугун билүүнү сурайт, анын саны 1 цифрасынын өлчөмү, суб-массивдеги 0 санынан бир гана көбүрөөк.

мисал

киргизүү:

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

Output:

5

Explanation:

0ден 4кө чейинки индекс, {1, 0, 1, 1, 0}, үчөө бар 1 жана эки 0. 1гө караганда 0дин дагы бир дагы саны.

киргизүү:

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

Output:

3

Explanation:

0ден 2ге чейин, {1, 0, 1}, эки 1 жана бир 0 бар. 1дөн 0ге көбүрөөк эсептөө.

Algorithm

  1. Картаны жарыялаңыз.
  2. Суммасын жана outputLengthти 0 кылып коюңуз.
  3. Массивди айланып өтүңүз, i = 0 ден i <nге чейин.
    1. Arr [i] 0ге барабар экендигин текшерип, эгер true болсо, анда -1ге кошуңуз.
    2. Кошумча суммага +1 кошуңуз.
    3. Эгерде суммасы барабар 1ге чейин, андан соң outputLength маанисин 1ге көбөйтүңүз.
    4. Башка учурда, эгер картада сумма камтылбаса, анда эгер чын болсо, анда анын суммасын жана учурдагы маанисин картага суммасы менен кошо коюңуз.
    5. Картада (сумма-1) камтылгандыгын текшериңиз.
    6. Эгерде outputLength i индексинен аз болсо (сумманын картадагы мааниси).
      1. Эгер чын болсо, анда outputLength i индексине чейин жаңыртыңыз.
  4. Чыгуунун узундугун кайтаруу.

түшүндүрүү

Биз жарыялайбыз карта. Ошол шартта сумманын маанисин жана учурдагы көрсөткүчтү, эгер шарт канааттандырса сактайбыз. Эки өзгөрүлмө алып, сумманы 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 менен жаңыртышыбыз керек жана биз outputLengthти кайтарып беребиз.

ишке ашыруу

Эң узак Subarray үчүн C ++ программасы, 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

Эң узак Subarray үчүн Javas программасы, 1s Count дан 0s дан көбүрөөк XNUMXs

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

Эң узак Subarray үчүн комплекстик анализ 1s санынан 0s көбүрөөк

Убакыт татаалдыгы

O (N) кайда "N"  массивдеги элементтердин саны.

Космостун татаалдыгы

O (N) кайда "N"  массивдеги элементтердин саны.