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


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

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

Σας δίδονται δύο πίνακες εκ των οποίων ο καθένας περιέχει δυαδικό αριθμό. Η δήλωση προβλήματος ζητά να βρει το μεγαλύτερο εύρος με το ίδιο άθροισμα σε δύο δυαδικές συστοιχίες, δηλαδή να ανακαλύψει την κοινή δευτερεύουσα συστοιχία μέγιστου μήκους από (i, j) με τέτοιο τρόπο ώστε το j να είναι μεγαλύτερο ή ίσο με το i και arr1 [ i] + arr1 [i + 1] + arr1 [i + 2] +…. + arr1 [j] = arr2 [i] + arr2 [i + 1] + arr2 [i + 2] +…. + arr2 [j].

Παράδειγμα

arr1[] = {1,0,1,0,0,0,1,1}

arr2[] = {1,0,1,0,1,1,0,1}
4

Επεξήγηση: Το μήκος του υψηλότερου κοινού εύρους είναι 4 επειδή στο δείκτη 0 έως 3 υπάρχει άθροισμα και των δύο υπο-συστοιχιών είναι ίσο.

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

arr1[] = {1, 0, 1, 0, 1, 0}

arr2[] = {0, 1, 1, 0, 0, 0}
4

Επεξήγηση: Το μήκος του υψηλότερου κοινού εύρους είναι 4 επειδή στο δείκτη 0 έως 3 υπάρχει άθροισμα και των δύο υπο-συστοιχιών που είναι ίσοι.

 

Αλγόριθμος

1. Declare an array of size n.
2. Find the difference of each element’s index of both of the arrays such that arr[i]=arr1[i]-arr2[i].
3. Declare the HashMap.
4. Set sum to 0 and maxLength to 0.
5. From i=0 to i<n.
    1. Add up the value of arr[i] and sum into the sum.
    2. Check if sum ==0, then update the maxLength=i+1.
    3. Check if the map contains the sum, then update the maxLength to the maximum between maxLength and i-key’s value.
    4. Else put the sum and its index into the map.
6. Return maxLength.

εξήγηση

Έχουμε δώσει δύο δυαδικές συστοιχίες, καθεμία από τις οποίες περιέχει τον δυαδικό αριθμό με τη μορφή 0 και 1. Πρέπει να βρούμε το μεγαλύτερο κοινό εύρος [i, j] έτσι ώστε το άθροισμα και των δύο συστοιχιών, στο συγκεκριμένο εύρος , είναι ίσο και το μεγαλύτερο μήκος της κοινής έκτασης. Γι 'αυτό, πηγαίνουμε σε εμάς το Hashing και έναν επιπλέον πίνακα στον οποίο θα αποθηκεύσουμε τη διαφορά κάθε διαφοράς του στοιχείου ευρετηρίου στο ith θέση του πίνακα που δημιουργήθηκε.

Δημιουργούμε έναν χάρτη, δεδομένου ότι πρόκειται να αποθηκεύσουμε την τιμή του νεοσύστατου πίνακα ως κλειδί στον χάρτη και το ευρετήριό του ως τιμή. Θα μάθουμε το μέγιστο αυτού του ευρετηρίου και θα το συγκρίνουμε με το μέγιστο μήκος που δημιουργήσαμε για να βρούμε και να αποθηκεύσουμε τη μέγιστη τιμή ως το μεγαλύτερο μήκος. Αλλά πριν από αυτό, παίρνουμε το arr [i] και το προσθέτουμε με το arr [i] και το άθροισμα και το αποθηκεύουμε στο άθροισμα. Θα ελέγξουμε εάν το άθροισμα είναι ίσο με 0, θα ενημερώσουμε το maxLength σε i + 1. Αυτό γίνεται για τον χειρισμό των τιμών στο τελευταίο στοιχείο ευρετηρίου.

Ελέγξτε εάν ο χάρτης περιέχει το άθροισμα, στη συνέχεια, ενημερώστε το μέγιστο μήκος, ανακαλύπτοντας το μέγιστο μεταξύ του μέγιστου μήκους και του ευρετηρίου - χάρτη[άθροισμα]. Αλλιώς βάλτε το άθροισμα και το ευρετήριο στο χάρτη. Ο πίνακας που δημιουργήσαμε και αρχικοποιήσαμε ως διαφορά μεταξύ των δύο συστοιχιών παίζει βασικό ρόλο. Μετά από αυτό, έχουμε την τιμή στο maxLength και επιστρέφουμε το maxLength.

 

Κωδικός για να βρείτε το μεγαλύτερο εύρος με το ίδιο άθροισμα σε δύο δυαδικές σειρές

Κωδικός C ++

#include<iostream>
#include<unordered_map>

using namespace std;

int longestCommonSum(int arr1[], int arr2[], int n)
{
    int arr[n];
    for (int i=0; i<n; i++)
        arr[i] = arr1[i] - arr2[i];

    unordered_map<int, int> hM;

    int sum = 0;

    int max_len = 0;
    for (int i = 0; i < n; i++)
    {
        sum += arr[i];

        if (sum == 0)
            max_len = i + 1;

        if (hM.find(sum) != hM.end())
            max_len = max(max_len, i - hM[sum]);

        else
            hM[sum] = i;
    }
    return max_len;
}

int main()
{
    int arr1[] = {0, 1, 0, 1, 1, 1, 1};
    int arr2[] = {1, 1, 1, 1, 1, 0, 1};
    int n = sizeof(arr1)/sizeof(arr1[0]);
    cout << longestCommonSum(arr1, arr2, n);
    return 0;
}
6

 

Κωδικός Java

import java.util.HashMap;

class LargestSubArr01
{
    public static int longestCommonSum(int[] arr1, int[] arr2, int n)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = arr1[i] - arr2[i];

        HashMap<Integer, Integer> hM = new HashMap<>();

        int sum = 0;
        int max_len = 0;

        for (int i = 0; i < n; i++)
        {
            sum += arr[i];

            if (sum == 0)
                max_len = i + 1;

            if (hM.containsKey(sum))
                max_len = Math.max(max_len, i - hM.get(sum));

            else
                hM.put(sum, i);
        }
        return max_len;
    }
    public static void main(String args[])
    {
        int[] arr1 = {0, 1, 0, 1, 1, 1, 1};
        int[] arr2 = {1, 1, 1, 1, 1, 0, 1};
        int n = arr1.length;
        System.out.println(longestCommonSum(arr1, arr2, n));
    }
}
6

 

Ανάλυση πολυπλοκότητας

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

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα. Εδώ, έχουμε διασχίσει τον πίνακα μία φορά και αφού χρησιμοποιήσαμε έναν χάρτη χωρίς διάταξη. Οι λειτουργίες εισαγωγής, διαγραφής και αναζήτησης έχουν πολύπλοκη ώρα O (1). Έτσι, ολόκληρος ο αλγόριθμος για το μεγαλύτερο χρονικό διάστημα με το ίδιο άθροισμα σε δύο δυαδικές σειρές έχει γραμμική πολυπλοκότητα χρόνου.

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

Δεδομένου ότι χρησιμοποιήσαμε το χάρτη unordered_map ή hash, έχουμε επίσης γραμμική πολυπλοκότητα χώρου. O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.