İki Binary Arrays II-də eyni Cəm ilə ən uzun aralıq

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Accenture Cisco Həqiqətən Kuliza SAP Laboratoriyaları Yandex
Geyim Sükut HashingBaxılıb 320

Problem bəyanat

“İki İkili massivdə eyni cəmi olan ən uzun aralıq II” problemində iki ikili verdik seriallar Eyni ölçülü “a” və “b”. Ən uzunluğu eyni cəm ilə iki massivdə çap etmək üçün bir proqram yazın. Aşağıdakı nümunədə bu açıq şəkildə izah edilə bilər.

Giriş Formatı

Tam bir n dəyəri olan ilk və yalnız bir sətir.

N boşluqla ayrılmış “a” dəyərini (0 və ya 1) ehtiva edən ikinci sətir.

Üçüncü sətirdə “b” nin boşluqla ayrılmış n dəyəri (o və ya 1) var.

Çıxış formatı

İki massivdə eyni cəmi olan ən uzun aralığını ifadə edən bir tam dəyər ehtiva edən ilk və yalnız bir sətir.

Məhdudiyyətlər

  • 1 <= n <= 10 ^ 6
  • a [i], b [i] 0 və ya 1 olmalıdır.

misal

4
0 1 0 1
1 0 0 0
3

Explanation: Yuxarıdakı nümunədə, indeks 0-dan 3-ə qədər iki massivdəki indeks 0 ilə 3 arasındakı elementlərin cəmi eynidir.

İki İkili massivdə eyni cəmi olan ən uzun aralığın alqoritmi II

Məntiqin həyata keçirilməsi aşağıdakı müşahidələrə əsaslanır.

  • Cəmi n element olduğu üçün hər iki massiv üçün maksimum cəm ​​n-dir.
  • İki cəmi arasındakı fərq -n üçün n. Beləliklə, fərqin ümumi 2n + 1 mümkün dəyəri var.
  • İki massivin prefiksi cəmləri arasındakı fərqlər iki nöqtədə eyni olarsa, bu iki nöqtə arasındakı subarrays eyni cəmə sahibdir.

İndi yuxarıdakı üç məqamı nəzərə alaraq alqoritm hissəsinə keçin:

  1. Fərqlərin mümkün olan bütün dəyərlərinin başlanğıc nöqtələrini saxlamaq üçün 2n + 1 ölçülü köməkçi bir sıra yaradın (Fərqlərin mümkün dəyərlərinin -n ilə n arasında dəyişdiyini unutmayın, yəni ümumi 2n + 1 mümkün dəyərlər var)
  2. Bütün fərqlərin başlanğıc nöqtələrini -1 olaraq başlatın.
  3. Initialize maxLen 0 olaraq və hər iki massivin prefiksi cəmi 0, presum1 = 0, presum2 = 0
  4. Hər iki massivi i = 0-dan n-1-ə keçir.
    1. Prefiks cəmlərini yeniləyin: preSum1 + = arr1 [i], preSum2 + = arr2 [i]
    2. Cari prefiks cəmlərinin fərqini hesablayın: cərəyan_diff = preSum1 - preSum2
    3. Fərq massivində indeks tapın: diffIndex = n + curr_diff // curr_diff mənfi ola bilər və -n-ə qədər gedə bilər
    4. If curr_diff 0, i + 1 indiyə qədər maxLen-dir
    5. Else əgər curr_diff ilk dəfə görünür, yəni cari fərqin başlanğıc nöqtəsi -1, sonra başlanğıc nöqtəsini i kimi yeniləyin
    6. Daha (curr_diff ilk dəfə görünmür), sonra i nöqtəsini bitmə nöqtəsi hesab edin və cari eyni cəmin uzunluğunu tapın. Bu uzunluq daha çoxdursa, maxLen-i yeniləyin
  5. MaxLen qayıdın.

Həyata keçirilməsi

İki İkili Array II-də eyni Cəmi olan ən uzun müddət üçün C ++ Proqramı II

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

int main() 
{ 
  int n;
  cin>>n;
  int a[n];
  int b[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  for(int i=0;i<n;i++)
  {
      cin>>b[i];
  }
  int maxLen = 0; 
  int ps1 = 0, ps2 = 0; 
  int temp[2*n+1]; 
  memset(temp, -1, sizeof(temp)); 
  for (int i=0; i<n; i++) 
  { 
    ps1 += a[i]; 
    ps2 += b[i]; 
    int curr_diff = ps1 - ps2; 
    int diff = n + curr_diff; 
    if (curr_diff == 0) 
      maxLen = i+1; 
    else if ( temp[diff] == -1) 
      temp[diff] = i; 
    else
    { 
      int len = i - temp[diff]; 
      if (len > maxLen) 
        maxLen = len; 
    } 
  } 
  cout<<maxLen<<endl; 
  return 0; 
} 

İki İkili Array II-də eyni cəmlə ən uzun müddət üçün Java proqramı

import java.util.ArrayList;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        int a[]= new int[n];
        int b[]= new int[n];
        for(int i=0;i<n;i++)
        {
            a[i]=sr.nextInt();
        }
        for(int i=0;i<n;i++)
        {
            b[i]=sr.nextInt();
        }
        int maxLen = 0; 
  int ps1 = 0, ps2 = 0; 
  int temp[] = new int [2*n+1]; 
  for(int i=0;i<2*n+1;i++)
        {
            temp[i]=-1;
        }
  for (int i=0; i<n; i++) 
  { 
    ps1 += a[i]; 
    ps2 += b[i]; 
    int curr_diff = ps1 - ps2; 
    int diff = n + curr_diff; 
    if (curr_diff == 0) 
      maxLen = i+1; 
    else if ( temp[diff] == -1) 
      temp[diff] = i; 
    else
    { 
      int len = i - temp[diff]; 
      if (len > maxLen) 
        maxLen = len; 
    } 
  } 
  System.out.println(maxLen); 
    }
}
10
1 0 0 0 1 1 0 1 1 0
0 0 1 0 1 1 0 1 0 0
9

İki İkili Array II-də eyni Cəm ilə ən uzun müddət üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n) burada n verilən “a” və ya “b” massivinin ölçüsüdür. Burada serialı ziyarət edirik və bir mövqedəki cəmi fərqini tapırıq.

Kosmik Mürəkkəblik

O (n)  çünki indeksin saxlanılması üçün istifadə etdiyimiz bir temp seriyası elan edirik.

Translate »