İki İkili massivdə eyni Cəmi olan ə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 33

Problem bəyanat

Hər biri ikili saydan ibarət olan iki sıra verilir. Problem ifadəsi, iki ikili massivdə eyni cəmi olan ən uzun aralığın tapılmasını, yəni (i, j) -dən maksimum uzunluqlu ümumi alt arrayın j-nin i və arr1-dən çox və ya bərabər olduğu şəkildə tapılmasını xahiş edir. i] + arr1 [i + 1] + arr1 [i + 2] +…. + arr1 [j] = arr2 [i] + arr2 [i + 1] + arr2 [i + 2] +…. + arr2 [j].

misal

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

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

İzahat: Ən yüksək ümumi aralığın uzunluğu 4-dür, çünki 0-dan 3-dək indeksdə alt dizilərin hər ikisinin cəmi bərabərdir.

İki İkili massivdə eyni Cəmi olan ən uzun aralıqPin

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

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

İzahat: Ən yüksək ümumi aralığın uzunluğu 4-dür, çünki 0-dan 3-dək indeksdə hər iki alt massivin cəmi bərabərdir.

 

Alqoritm

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.

Izahat

Hər biri 0 və 1 şəklində ikili ədədi ehtiva edən iki ikili sıra verdik. [İ, j] -nin ən uzun ümumi aralığını tapmalıyıq ki, hər iki massivin cəmi, həmin aralıqda , bərabərdir və ümumi uzunluğun ən uzunluğu. Bunun üçün hər bir i'th indeks elementinin fərqinin fərqini yaradılan massivin i'ci mövqeyində saxlayacağımız Hashing və əlavə bir sıra bizə gedirik.

Yeni yaradılan massivin dəyərini xəritəyə açar olaraq, indeksini isə dəyər olaraq saxlayacağımız bir xəritə yaradırıq. Bu indeksin maksimumunu tapacağıq və maksimum dəyəri ən uzun uzunluqda tapmaq və saxlamaq üçün yaratdığımız maxLength ilə müqayisə edəcəyik. Ancaq bundan əvvəl [i] arrasını götürürük və arr [i] ilə əlavə edirik və cəmdə saxlayırıq. Cəmin 0-a bərabər olub olmadığını yoxlayacağıq, maxLength i + 1-ə qədər yeniləyin. Bu, son indeks elementindəki dəyərləri idarə etmək üçündür.

Xəritədə cəmi olub olmadığını yoxlayın, sonra maxLength və index arasındakı maksimumu taparaq maksimum uzunluğu yeniləyin - xəritə[cəmi]. Başqa cəmi və indeksi xəritəyə qoydu. Hər iki massiv arasındakı fərq olaraq hazırladığımız və işə saldığımız sıra əsas rol oynayır. Bundan sonra maxLength dəyərinə sahibik və maxLength qaytarırıq.

 

İki İkili massivdə eyni Cəmi olan ən uzun aralığı tapmaq üçün kod verin

C ++ kodu

#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 kodu

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

 

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara "N" massivdəki elementlərin sayıdır. Budur, biz serialı bir dəfə keçdik və sıralanmamış bir xəritədən istifadə etdiyimiz üçün. Yerləşdirmə, Silmə və axtarış əməliyyatları O (1) vaxt mürəkkəbliyinə malikdir. Beləliklə, iki ikili massivdə eyni cəmi olan ən uzun aralığın bütün alqoritmi xətti zaman mürəkkəbliyinə malikdir.

Kosmik Mürəkkəblik

Sırasız_map və ya hash xəritəsini istifadə etdiyimiz üçün, xətti məkan mürəkkəbliyimiz də var. O (n) hara "N" massivdəki elementlərin sayıdır.

Translate »