Bitişik Array

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon MakeMyTrip Morgan Stanley Paytm
Hashing Sürüşmə pəncərəBaxılıb 32

Verilmiş bir array yalnız 0 və 1 saylarından ibarətdir. O və 1-lərdən ibarət olan ən uzun bitişik alt dizinin uzunluğunu bərabər şəkildə tapmalıyıq.

misal

Input

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

Buraxılış

6

Izahat

Ən uzun bitişik alt sıra qırmızı ilə işarələnmişdir [0,1,0,1,0,0,1] və uzunluğu 6-dır.

Alqoritm

  1. Maxlen dəyərini 0 olaraq təyin edin.
  2. İki döngədən istifadə edin, ilk döngədə zer_count 0, one_count 0 qoyun.
  3. Əgər dəyəri müəyyən bir indeksdə bir sıra 0 olduğu aşkar edildikdə sıfır sayını 1 artırın.
  4. Digər yeniləmə və one_count'u 1 artırın.
  5. Hər təkrarlamada zero_count bir_count-a bərabər olub olmadığını yoxlayır, bərabərdirsə, (maxlen və j-i + 1) arasında daha böyük olanı tapın.
  6. Maxlen qayıdın

Izahat

Əsas fikrimiz, sıfır və yeganə olan ən uzun bitişik subarrayın uzunluğunu tapmaqdır, buna görə əsas diqqətimiz bu uzunluğu tapmaqdır.

Buna görə, loop üçün iç içə istifadə edəcəyik. Xarici döngədə zero_count və one_count dəyərini 0-a başlayırıq, çünki daxili döngüdən çıxdıqda hər təkrarlamadan sonra hamısını yenidən yoxlamaq üçün zero_count və one_count təzə dəyərlərinə ehtiyacımız var. Dizinin uzunluğuna çatana qədər döngü üzərində təkrarlanacağıq.

İndi serialın hər bir dəyərini yoxlamaq üçün gedir, əgər arr [index] -in 0-a və ya 1-ə bərabər bir dəyəri varsa 0-a bərabərdir, onda zero_count dəyərini 1 artırın və ya arr [index] -in dəyərini artırın 1 olduqda, yenilənir və one_count dəyərini 1 artırır.

İndi blok növbəti sıfır sayının bir_sayta bərabər olub olmadığını yoxlayacaq, əgər bərabərdirsə, onda maxlen və j-i + 1 arasındakı daha böyük ədədi tapın və daha böyük sayını maxlenə saxla.

misal

Fərz edək ki, verilmiş sıra: arr [] = {1,0,0,1,0,1,0}

zero_count = 0, one_count = 0, maxlen = 0

i = 0 olduqda, => j = i

j = 0

arr [j] -də 0-a bərabər deyil, onda one_count ++, one_count = 1 deməkdir

j = 1

Arr [j] -də 0-a bərabər, onda zero_count ++, zero_count = 1 deməkdir

Blokun yerinə yetirildiyi təqdirdə bu yerdə maxlen və j-i + 1 arasında daha böyük bir nəticə vermir və maxlen-də 2-yə qayıdır.

j = 2

Arr [j] -də 0-a bərabər, onda zero_count ++, zero_count = 2 deməkdir

j = 3

Arr [j] -də 0-a bərabər olmayan, onda one_count ++, one_count = 2 deməkdir

Blok yerinə yetirildiyi təqdirdə bu yerdə maxlen və j-i + 1 arasında daha böyük bir nəticə vermir və maxlen-də 4-i qaytarır.

j = 4

Arr [j] -də 0-a bərabər, onda zero_count ++, zero_count = 3 deməkdir

j = 5

Arr [j] -də 0-a bərabər olmayan, onda one_count ++, one_count = 3 deməkdir

Blok yerinə yetirildiyi təqdirdə bu yerdə maxlen və j-i + 1 arasında daha böyük bir nəticə vermir və maxlen-də 6-i qaytarır.

j = 6

Arr [j] -də 0-a bərabər, onda zero_count ++, zero_count = 4 deməkdir

Və bütün şərtlər uğursuz oluncaya qədər döngəni təkrarlamağa davam edir.

Və maxleni 6 olaraq qaytarın.

Həyata keçirilməsi

Bitişik Array üçün C ++ proqramı

#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

Bitişik Array üçün Java proqramı

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

Bitişik Array üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N * N) hara N verilmiş massivin ölçüsüdür.

Kosmik Mürəkkəblik

O (1) çünki burada əlavə yerdən istifadə etmirik.

arayış

Translate »