Μεγαλύτερο διάστημα με το ίδιο άθροισμα σε δύο δυαδικές συστοιχίες II


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις Accenture Cisco Πράγματι Κουλίζα SAP Labs Yandex
Παράταξη Χασίσι Hashing

Δήλωση προβλήματος

Στο πρόβλημα "Μεγαλύτερο διάστημα με το ίδιο άθροισμα σε δύο δυαδικές συστοιχίες II", δώσαμε δύο δυαδικά συστοιχίες "A" και "b" με το ίδιο μέγεθος. Γράψτε ένα πρόγραμμα για να εκτυπώσετε το μεγαλύτερο διάστημα με το ίδιο άθροισμα σε δύο πίνακες. Αυτό μπορεί να εξηγηθεί με σαφήνεια στο παρακάτω παράδειγμα.

Μορφή εισόδου

Η πρώτη και μοναδική γραμμή που περιέχει ακέραια τιμή n.

Δεύτερη γραμμή που περιέχει n διαχωρισμένες με διαστήματα τιμές (0 ή 1) του "a".

Η τρίτη γραμμή περιέχει επίσης τιμές διαχωρισμένες με κενό διάστημα (o ή 1) του "b".

Μορφή εξόδου

Η πρώτη και μοναδική γραμμή που περιέχει ακέραια τιμή που υποδηλώνει τη μεγαλύτερη απόσταση με το ίδιο άθροισμα σε δύο πίνακες.

Περιορισμοί

  • 1 <= n <= 10 ^ 6
  • a [i], b [i] πρέπει να είναι 0 ή 1.

Παράδειγμα

4
0 1 0 1
1 0 0 0
3

Επεξήγηση: Στο παραπάνω παράδειγμα, από το ευρετήριο 0 έως 3 το άθροισμα των στοιχείων από το ευρετήριο 0 έως 3 στις δύο συστοιχίες είναι το ίδιο.

Αλγόριθμος για το μεγαλύτερο εύρος με το ίδιο άθροισμα σε δύο δυαδικές συστοιχίες II

Η εφαρμογή της λογικής βασίζεται στις παρακάτω παρατηρήσεις.

  • Δεδομένου ότι υπάρχουν συνολικά στοιχεία n, το μέγιστο άθροισμα είναι n και για τις δύο συστοιχίες.
  • Η διαφορά μεταξύ δύο αθροισμάτων ποικίλλει από -n προς την n. Υπάρχουν συνολικά 2n + 1 πιθανές τιμές διαφοράς.
  • Εάν οι διαφορές μεταξύ των αθροισμάτων προθέματος των δύο συστοιχιών γίνονται οι ίδιες σε δύο σημεία, τότε οι υπόγειες μεταξύ αυτών των δύο σημείων έχουν το ίδιο άθροισμα.

Τώρα, λαμβάνοντας υπόψη τα παραπάνω τρία σημεία μεταβείτε στο μέρος του αλγορίθμου:

  1. Δημιουργήστε έναν βοηθητικό πίνακα μεγέθους 2n + 1 για να αποθηκεύσετε τα σημεία εκκίνησης όλων των πιθανών τιμών διαφορών (Σημειώστε ότι οι πιθανές τιμές των διαφορών ποικίλλουν από -n σε n, δηλαδή, υπάρχουν συνολικά 2n + 1 πιθανές τιμές)
  2. Αρχικοποιήστε τα σημεία εκκίνησης όλων των διαφορών ως -1.
  3. αρχικοποίηση maxLen ως 0 και αθροίσματα προθέματος και των δύο συστοιχιών ως 0, προSum1 = 0, προSum2 = 0
  4. Διασχίστε και τις δύο συστοιχίες από i = 0 έως n-1.
    1. Ενημέρωση αθροισμάτων προθέματος: preSum1 + = arr1 [i], preSum2 + = arr2 [i]
    2. Υπολογίστε τη διαφορά των τρέχοντων αθροισμάτων προθέματος: curr_diff = preSum1 - preSum2
    3. Εύρεση ευρετηρίου σε πίνακα διαφορών: diffIndex = n + curr_diff // curr_diff μπορεί να είναι αρνητικό και μπορεί να φτάσει μέχρι -n
    4. If Το curr_diff είναι 0, τότε το i + 1 είναι maxLen μέχρι στιγμής
    5. Αλλιώς Το curr_diff εμφανίζεται την πρώτη φορά, δηλαδή, το σημείο εκκίνησης της τρέχουσας διαφοράς είναι -1 και, στη συνέχεια, ενημερώστε το σημείο εκκίνησης ως i
    6. Αλλού (Το curr_diff ΔΕΝ εμφανίζεται την πρώτη φορά), τότε θεωρήστε το ως τελικό σημείο και βρείτε το μήκος του τρέχοντος ίδιου αθροίσματος. Εάν αυτό το μήκος είναι μεγαλύτερο, ενημερώστε το maxLen
  5. Επιστροφή maxLen.

Εκτέλεση

Πρόγραμμα C ++ για μεγαλύτερο χρονικό διάστημα με το ίδιο άθροισμα σε δύο δυαδικές συστοιχίες 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; 
} 

Πρόγραμμα Java για μεγαλύτερο χρονικό διάστημα με το ίδιο άθροισμα σε δύο δυαδικές συστοιχίες II

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

Ανάλυση πολυπλοκότητας για το μεγαλύτερο εύρος με το ίδιο άθροισμα σε δύο δυαδικές συστοιχίες II

Χρόνος πολυπλοκότητας

O (n) όπου n είναι το μέγεθος του δεδομένου πίνακα "a" ή "b". Εδώ επισκεφτούμε τον πίνακα και βρίσκουμε τη διαφορά του αθροίσματος προθέματος σε μια θέση.

Διαστημική πολυπλοκότητα

O (n)  γιατί δηλώνουμε έναν πίνακα temp που χρησιμοποιούμε για την αποθήκευση του ευρετηρίου.