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.
Mündəricat
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
- Maxlen dəyərini 0 olaraq təyin edin.
- İki döngədən istifadə edin, ilk döngədə zer_count 0, one_count 0 qoyun.
- Ə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.
- Digər yeniləmə və one_count'u 1 artırın.
- 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.
- 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.
