Үзгүлтүксүз Array  


Кыйынчылык деңгээли орто
Көп суралган Amazon MakeMyTrip Морган Стэнли Paytm
Hashing Жылма терезе

Берилген согуштук тизме 0 жана 1 сандарынан гана турат. О жана 1ден турган эң узун чектеш суб-массивдин узундугун бирдей табышыбыз керек.

мисал  

кирүү

arr = [0,1,0,1,0,0,1]

продукция

6

түшүндүрүү

Эң узун чектеш суб-массив кызыл менен белгиленген [0,1,0,1,0,0,1] жана анын узундугу 6.

Algorithm  

  1. Маклендин маанисин 0 деп коюңуз.
  2. Эки циклди колдонуңуз, биринчи циклде zer_count 0, one_count 0 деп белгиленди.
  3. Эгерде массив белгилүү бир индекс боюнча 0 деп табылса, анда нөл_санааны 1ге көбөйтөт.
  4. Башка жаңыртуу жана one_count 1ге көбөйтүү.
  5. Ар бир кайталоо учурунда zero_count бир_countга барабар, эгер барабар болсо, анда (maxlen жана j-i + 1) ортосунда чоңураак жоктугун табыңыз
  6. Maxlen кайтуу

түшүндүрүү  

Биздин негизги идея - эң узун чектеш субарренин узундугун табуу, ал нөлгө бар жана бирөө, андыктан биздин негизги максатыбыз ушул узундукту табуу.

Ошондуктан, nested for loop колдонобуз. Тышкы циклде биз zero_count жана one_count маанилерин 0ге коебуз, анткени ар бир итерациядан кийин, ички циклден чыкканда, биз аны кайра текшерүү үчүн zero_count жана one_count жаңы маанилерине ээ болобуз. Массивдин узундугу жеткенге чейин циклдин үстүнөн кайталайбыз.

ошондой эле
Массивди берилген аралыктагы үч тараптуу бөлүү

Эми ал массивдин ар бир чоңдугун текшерет, эгер arr [индекси] 0 же 1 маанисине ээ болсо, анда 0ге барабар болсо, анда zero_count маанисин 1ге көбөйтүп же көбөйтсөк же arr [index] болсо 1 деп табылса, анда ал one_count маанисин 1ге көбөйтөт жана көбөйтөт.

Эми, кийинки блок, zero_count one_countга барабар экендигин текшерет, эгер бар болсо, анда maxlen менен j-i + 1дин ортосундагы чоңураак санды таап, чоңун maxlenге сактайт.

мисал

Массив берилген дейли: arr [] = {1,0,0,1,0,1,0}

zero_count = 0, one_count = 0, maxlen = 0

i = 0 болгондо, => j = i

j = 0

arr [j] де 0ге барабар эмес, анда one_count ++, бир_сана = 1 дегенди билдирет

j = 1

Arr [j] 0го барабар, анда zero_count ++, zero_count = 1 дегенди билдирет

Бул жерде, эгер блок аткарылса, анда ал maxlenдин ортосунда чоң болбойт, ал эми j-i + 1 жана maxlenде 2ди кайтарат

j = 2

Arr [j] 0го барабар, анда zero_count ++, zero_count = 2 дегенди билдирет

j = 3

Arr [j] 0го барабар болбосо, анда one_count ++, one_count = 2 дегенди билдирет

Бул жерде, эгер блок аткарылса, анда ал maxlenдин ортосунда чоң болбойт, ал эми j-i + 1 жана maxlenде 4тү кайтарат.

j = 4

Arr [j] 0го барабар, анда zero_count ++, zero_count = 3 дегенди билдирет

j = 5

Arr [j] 0го барабар болбосо, анда one_count ++, one_count = 3 дегенди билдирет

Бул жерде, эгер блок аткарылса, анда ал maxlenдин ортосунда чоң болбойт, ал эми j-i + 1 жана maxlenде 6тү кайтарат.

j = 6

Arr [j] 0го барабар, анда zero_count ++, zero_count = 4 дегенди билдирет

Бардык шарттар аткарылгыча, ал циклди кайталап турат.

Ал эми maxlenди 6 деп кайтарыңыз.

ишке ашыруу  

Үзгүлтүксүз Array үчүн C ++ программасы

#include <iostream>
using namespace std;
int contiguous_Array(int arr[], int n)
{
    int i,j,maxlen=0;
    for( i = 0 ; i < n ; i++)
    {
        int zero_count=0,one_count=0;
        for(j = i ; j < n ; j++)
        {
            if( arr[j] == 0 )
            {
                zero_count++;
            }
            else
            {
                one_count++;
            }
            if(zero_count==one_count)
            {
                maxlen=std::max(maxlen,j-i+1);
            }
        }
    }
    return maxlen;
}
int main()
{
    int arr[]= {1,0,0,1,0,1,0};
    int n=sizeof(arr)/sizeof(arr[0]);
    cout <<contiguous_Array(arr,n)<< endl;
    return 0;
}
6

Үзгүлтүксүз Array үчүн Java программасы

public class Contiguous_Array {

  public static int solution(int[] arr) {

    int maxlen = 0;

    for (int i = 0; i<arr.length; i++) {

      int zero_count = 0, one_count = 0;

      for (int j = i; j<arr.length; j++) {

        if (arr[j] == 0) {
          zero_count++;
        } else {
          one_count++;
        }
        if (zero_count == one_count) {

          maxlen = Math.max(maxlen, j - i + 1);

        }
      }
    }
    return maxlen;
  }
  public static void main(String args[]) {

    int[] arr = new int[] {
      0, 1, 0, 1, 0, 0, 1
    };

    System.out.println(solution(arr));

  }
}
6

Аралаш массивдин татаалдыгын талдоо  

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

O (N * N) кайда N берилген массивдин көлөмү.

ошондой эле
Түстөрдү сорттоо

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

O (1) анткени биз бул жерде ашыкча орун колдонбойбуз.

шилтеме