Շարունակ զանգված


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon MakeMyTrip- ը Morgan Stanley Paytm
Հեշինգ Սահող պատուհան

Հաշվի առնելով ան դասավորություն բաղկացած է միայն 0-ից և 1-ից: Մենք պետք է գտնենք ամենաերկար հարևան ենթախմբի երկարությունը, որը հավասարապես բաղկացած է o -ներից և 1-ից:

Օրինակ

Մուտքային

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

Արտադրողականություն

6

բացատրություն

Ամենաերկարը հարակից ենթա-զանգված նշվում է կարմիրով [0,1,0,1,0,0,1], իսկ դրա երկարությունը 6 է:

Ալգորիթմ

  1. Մաքսլենի արժեքը դնել 0:
  2. Օգտագործեք երկու օղակ, առաջին օղակում սահմանեք zer_count- ը 0, one_count- ը 0:
  3. Եթե ​​արժեքը զանգվածը որոշակի ցուցանիշով պարզվել է, որ 0 է, ապա ավելացրեք զրո_հաշիվը 1-ով:
  4. Այլապես թարմացրեք և ավելացրեք մեկ_հաշիվը 1-ով:
  5. Յուրաքանչյուր կրկնության ժամանակ ստուգեք, արդյոք զրո_հաշիվը հավասար է մեկ_հաշվի, եթե հավասար է, ապա պարզեք ավելի մեծ ոչ-ը (maxlen և j-i + 1)
  6. Վերադարձիր մաքսլեն

բացատրություն

Մեր հիմնական գաղափարն է գտնել ամենաերկար հարևան ենթախմբի երկարությունը, որն ունի զրո և միայն մեկը, ուստի մեր հիմնական նպատակն է գտնել այդ երկարությունը:

Հետեւաբար, մենք մտադիր ենք օգտագործել հանգույցի համար տեղադրված: Արտաքին օղակում զրոյական_հաշվարկի և մեկ_հաշվի արժեքը նախանշում ենք 0-ին, քանի որ ներքին կրկնությունից դուրս գալուց հետո յուրաքանչյուր կրկնությունից հետո մեզ անհրաժեշտ են զրո_հաշվարկի և մեկ_հաշվի թարմ արժեքներ `նորից ամբողջը ստուգելու համար: Մենք պատրաստվում ենք կրկնել օղակի վրայով, քանի դեռ չի հասել զանգվածի երկարությունը:

Այժմ այն ​​պատրաստվում է ստուգել զանգվածի յուրաքանչյուր արժեք, եթե arr [index] - ը 0 կամ 1 արժեք ունի, եթե 0-ի արժեք ունի, ապա թարմացրեք և ավելացրեք զրո_հաշվարկի արժեքը 1-ով կամ եթե arr- ի արժեքը [index] գտնում է, որ 1 է, ապա այն թարմացնում և ավելացնում է մեկի_հաշվի արժեքը 1-ով:

Հիմա, եթե հաջորդ բլոկը պատրաստվում է ստուգել, ​​արդյոք զրոյական_հաշիվը հավասար է մեկ_հաշվի, եթե հավասար է, ապա պարզեք, թե որն է ավելի մեծ թիվ 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-ին, ապա մեկ_հաշիվ ++, նշանակում է մեկ_հաշիվ = 1

j = 1

Arr [j] - ին հավասար է 0-ի, ապա zero_count ++, նշանակում է zero_count = 1

Այս տեղում հաջորդը, եթե բլոկը գործարկվի, այն ավելի մեծ ոչ է տալիս maxlen- ի և j-i + 1- ի և վերադարձնում 2-ը maxlen- ի մեջ:

j = 2

Arr [j] - ին հավասար է 0-ի, ապա zero_count ++, նշանակում է zero_count = 2

j = 3

Arr [j] - ին հավասար չէ 0-ին, ապա մեկ_հաշիվ ++, նշանակում է մեկ_հաշիվ = 2

Այս տեղում հաջորդը, եթե բլոկը գործարկվի, այն ավելի մեծ ոչ է տալիս maxlen- ի և j-i + 1- ի միջև և վերադարձնում 4-ը maxlen- ում:

j = 4

Arr [j] - ին հավասար է 0-ի, ապա zero_count ++, նշանակում է zero_count = 3

j = 5

Arr [j] - ին հավասար չէ 0-ին, ապա մեկ_հաշիվ ++, նշանակում է մեկ_հաշիվ = 3

Այս տեղում հաջորդը, եթե բլոկը գործարկվի, այն ավելի մեծ ոչ է տալիս maxlen- ի և j-i + 1- ի միջև և վերադարձնում 6-ը maxlen- ում:

j = 6

Arr [j] - ին հավասար է 0-ի, ապա zero_count ++, նշանակում է zero_count = 4

Եվ այն անընդհատ կրկնում է օղակը, մինչև բոլոր պայմանները ձախողվեն:

Եվ վերադարձեք մաքսլենը որպես 6:

Իրականացման

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

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

Բարդության վերլուծություն հարակից զանգվածի համար

Timeամանակի բարդություն

O (N * N) որտեղ N տրված զանգվածի չափն է:

Տիեզերական բարդություն

Ո (1) քանի որ մենք այստեղ ոչ մի լրացուցիչ տարածք չենք օգտագործում:

Մանրամասն