0 və 1 bərabər sayda ən böyük subarray

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Facebook google Quora Robinlik
Geyim Sükut Hashing HashMapBaxılıb 477

Problem bəyanat

“Bərabər sayı 0 və 1-lə bərabər olan ən böyük subarray” problemində bir array yalnız 0 və 1-i ehtiva edən a [] bərabər bərabərlikdə 0 və 1-lərlə ən böyük alt dizini tapın və ən böyük alt dizinin başlanğıc və son indeksini yazdırın.

Giriş Formatı

Tam bir N dəyəri olan ilk sətir.

N boşluqla ayrılmış tam ədədi (0 və ya 1) ehtiva edən ikinci sətir.

Çıxış formatı

0 və 1-lərin bərabər_sayıları ilə ən böyük alt sətrin uzunluğunu ifadə edən bir tamsayı dəyəri olan ilk və yalnız bir sətir.

Məhdudiyyətlər

  • 1 <= N <= 10 ^ 5
  • 0 <= a [i] <= 1

misal

7
0 1 0 1 1 0 0
6

Yanaşma

1-lə qarşılaşdıqda cəmi 1-i, 0-lu qarşılaşdıqda cəmi -1-i əlavə etdikdə, cəmi birləşdirmək üçün dəyişən bir cəmdən istifadə edirik. Bütün cəmi xəritədə cəmi ilə açar, indeks kimi dəyər kimi, əsas dəyər cütü kimi saxlayırıq. Əvvəllər kəşf edilmiş bir cəmlə qarşılaşsaq, bu cəmin son əmələ gəlməsi ilə bu meydana gəlməsi arasında deməkdir ki, bərabər say 1 və -1 olur. Hamısının maksimumunu alırıq.

0-a bərabər olan dəyişən cəmi götürək və massivdən keçək. Hər dəfə 0-a rast gəldikdə, 1-ə rast gəldikdə cəmi 1-ə endiririk və cəmi 1-ə artırırıq. Sayı 0-a bərabər olduqda bərabər 1 və 0-ə bərabər bitişik subarrayımız olduğuna inanmaq asandır.

Bir sıra ardıcıllığı götürək [0, 0, 1, 0, 0, 0, 1, 1].

0 və 1 bərabər sayda ən böyük subarrayPin

Cəmi 0-dan başlayır və belə davam edir -1, -2, -1, -2, -3, -4, -3, -2

Şəkildən, eyni y oxu dəyərinə sahib olan iki nöqtənin bu iki nöqtə arasındakı ardıcıllığı bərabər 0 və 1-ə bərabər olduğunu göstərdiyini asanlıqla başa düşə bilərik.

0 və 1-ə bərabər olan subarray cəmi -2, -1 və -3 olduqda başladı və bitdi. Ən uzun cəmi -2-yə bərabər olduqda.

Həyata keçirilməsi

0 və 1 bərabər sayda olan ən böyük subarray üçün C ++ proqramı

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  map<int,int> m;
    int ans=0,sum=0;
    for(int i=0;i<n;i++){
        int x = a[i];
        sum+=(x==1)?1:-1;
        
        if(sum==0){
        	ans =max(ans,i+1);
        }
        if(m.count(sum)){
            ans = max(ans,i-m[sum]);
        }else{
            m[sum]=i;
        }
    }
    cout<<ans<<endl;
  return 0;
}

0 və 1 bərabər sayda olan ən böyük subarray üçün Java proqramı

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        int ans = max_length(arr,n);
        System.out.println(ans);
        
  }
  
  public static int max_length(int[] arr,int n){
    Map<Integer, Integer> m = new HashMap<>();
    	int mx = 0, cnt = 0;
    	for(int i = 0;i < arr.length;i++) {
    		cnt+=(arr[i] == 1)?1:-1;
    		if(cnt == 0)
    			mx = Math.max(mx, i+1);    		
    		if(m.containsKey(cnt)) {
    			mx = Math.max(mx, i - m.get(cnt));
    		} else 
    			m.put(cnt, i);
    	}
    	return mx;
  }
}
9
0 1 1 0 0 1 1 1 0
6

0 və 1 bərabər sayda bərabər olan ən böyük subarray üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n) hara n verilmiş massivin ölçüsüdür. Burada bütün massivi yalnız bir dəfə keçirik və hər bir element üçün əməliyyatı sabit vaxtda həyata keçiririk. Buna görə bizi xətti zaman mürəkkəbliyinə aparır.

Kosmik Mürəkkəblik

O (n) hara n verilmiş massivin ölçüsüdür. Saxlamaq üçün xəritədən istifadə edirik cəmi ilə cəmi və dəyəri kimi göstəricisi ilə cəmi. Və xəritənin maksimum ölçüsü, massivin bütün dəyərlərinin 0 olduğu yerdir.

Translate »