Сумежны масіў Leetcode


Узровень складанасці серада
Часта пытаюцца ў амазонка facebook Google
масіў хэшавання

Пастаноўка праблемы

Праблема "Сумежны масіў Leetcode" абвяшчае, што вы атрымалі масіў a [] памеру n складаецца толькі з 1 і 0. Знайдзіце самая доўгая падмасіў у якіх колькасць 1 роўна колькасці 0.

Прыклад

Сумежны масіў Leetcode

a[ ] = {1, 0, 1, 1, 1, 0, 0}
1 to 6

Тлумачэнне: Выбар падмасіва з індэкса 1 да 6 дае нам лепшы вынік даўжыні 6. Суцэльны масіў ад 1 да 6 індэкса мае 3 нулі і 3. Тут мы разгледзелі індэксацыю на аснове 0.

a[ ] = {1, 1}
No such subarray

Падыход

Наіўны метад

Стварыць усе магчымыя падмасівы. Праверце, ці існуе які-небудзь падмасіў, у якім колькасць 1 роўна колькасці 0. Мы выкарыстоўваем два паказальнікі i і j для левай і правай мяжы падмасіва. Тады мы правяраем, ці ёсць сума падмасіва ад i да j сума = 0, пасля замены 0 на -1. Калі гэта праўда, мы знайшлі падмасіў, які адпавядае ўмовам. Цяпер мы абнаўляем наш адказ.

Алгарытм сумежнай задачы летакода масіва

1. Initialize a binary array a[] of size n and three variables sum, max=-1, and start.
2. Traverse through the array and update sum as -1 if a[i] is 0 else 1.
3. Traverse the inner loop and add -1 in sum if a[i] is 0 else 1.
4. Check if the sum is 0 and max is less than j-i+1, update max as j-i+1 and start as i.
5. Outside the loops check if max is -1 print "No such subarray" else print starting and ending index.

код

Праграма C ++ для вырашэння праблемы сумежнага масіва Leetcode
#include <bits/stdc++.h> 
using namespace std; 
  
int subArray(int a[], int n){ 
    int sum = 0; 
    int max = -1, start; 
  
    for(int i=0; i<n-1; i++){ 
        sum = (a[i]==0) ? -1 : 1; 
  
        for(int j=i+1; j<n; j++){ 
            (a[j]==0) ? (sum+=-1) : (sum+=1); 
  
            if(sum == 0 && max < j-i+1){ 
                max = j-i+1; 
                start = i; 
            } 
        } 
    } 
    if(max == -1) 
        cout<<"No such subarray"; 
    else
        cout<<start<<" to "<<start+max-1; 
  
    return max; 
} 
  
int main(){ 
    int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    subArray(a, n); 
    return 0; 
}
1 to 6
Праграма Java для вырашэння праблемы сумеснага масіва Leetcode
class LongestSubArray{
    int subArray(int a[], int n){ 
        int sum = 0; 
        int max = -1, start=0,end=0; 
        
        for(int i=0; i<n-1; i++){ 
            sum = (a[i]==0) ? -1 : 1; 
            
            for(int j=i+1; j<n; j++){ 
                if(a[j] == 0) 
                    sum += -1; 
                else
                    sum += 1;  
                
                if(sum == 0 && max < j-i+1){ 
                    max = j-i+1; 
                    start = i; 
                } 
            } 
        } 
        if(max == -1) 
            System.out.println("No such subarray");
        else
            end = start+max-1;
            System.out.println(start+" to "+end);
        
        return max; 
    } 
    public static void main(String[] args){ 
        LongestSubArray s = new LongestSubArray(); 
        int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
        int n = a.length; 
        
        s.subArray(a, n); 
    } 
}
1 to 6

Аналіз складанасці

Складанасць часу

Паколькі тут мы праходзілі масіў, захоўваючы ўказальнік. Мы дасягнулі шматзначнай складанасці часу  O (N2) дзе n - колькасць элементаў у дадзеным масіве a [].

Касмічная складанасць

O (1) таму што мы выкарыстоўвалі пастаянную дадатковую прастору. Мы стварылі толькі пастаянную колькасць зменных. Але не выкарыстаў ніякага масіва, акрамя пачатковага ўводу. Але праграма ў цэлым мае складанасць прасторы O (N), таму што мы выкарыстоўвалі масіў для захоўвання ўваходных элементаў.

Выкарыстанне хэш-карты

Алгарытм сумежнай задачы летакода масіва

1. Initialize a binary array a[] of size n.
2. Initialize an unordered map.
3. Traverse through the array and update the array value of the current index as -1 if current value if 0 else 1.
4. Traverse through the array and add the elements.
5. If the sum is 0, update max as i+1 and end as i.
6. Else Traverse map and update max as i - map(sum+n) and end as i if max is less than i - map(sum+n) else update map(sum+n) as i.
7. Traverse through the array and update the array value of the current index as 0 if current value is -1 else 1.
8. If the end is greater than -1 print starting and ending index.
9. Else print "No such subarray".

Тое, што мы зрабілі тут, проста кожны раз, калі нам трэба знайсці найбольшы падмасіў, які мае суму 0. Што мы робім, мы бярэм прэфіксную суму і правяраем нашу карту, калі дзесьці мы можам знайсці тую ж суму. Тады падмасіў, пачынаючы ад значэння, захаванага на карце +1, да бягучага індэкса мае суму 0. Тут мы выкарыстоўваем (sum + n) у якасці ключа. Але мы маглі б скарыстаць і суму непасрэдна. Але калі мы выкарыстоўваем (sum + n) у якасці ключа, мы можам таксама выкарыстоўваць масіў замест HashMap. Таму што тады мы можам запэўніць, што (sum + n)> = 0 і індэксацыя масіва пачынаецца з 0.

код

Праграма C ++ для вырашэння праблемы сумежнага масіва Leetcode
#include <bits/stdc++.h> 
using namespace std; 
  
int subArray(int a[], int n){ 
    
    unordered_map<int, int> hM; 
  
    int sum = 0, max = 0, end = -1; 
  
    for(int i=0; i<n; i++) 
        a[i] = (a[i] == 0) ? -1 : 1; 
  
    for(int i=0; i<n; i++){ 
        sum += a[i]; 
  
        if(sum == 0){ 
            max = i + 1; 
            end = i; 
        } 
  
        if(hM.find(sum + n) != hM.end()){ 
            if(max < i - hM[sum + n]){ 
                max = i - hM[sum + n]; 
                end = i; 
            } 
        } 
        else 
            hM[sum + n] = i; 
    } 
  
    for(int i=0; i<n; i++) 
        a[i] = (a[i] == -1) ? 0 : 1; 
        
    if(end>-1)
        cout<<end - max + 1<<" to "<<end; 
    else
        cout<<"No such subarray";
    return max; 
} 
  
int main(){ 
    int a[] = {1, 0, 1, 1, 1, 0, 0}; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    subArray(a, n); 
    return 0; 
} 
1 to 6
Праграма Java для вырашэння праблемы сумеснага масіва Leetcode
import java.util.HashMap;

class LongestSubArray{
    int subArray(int a[], int n){ 
        
        HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>(); 
  
        int sum = 0, max = 0, end = -1, start = 0; 
  
        for(int i=0; i<n; i++){ 
            a[i]=(a[i]==0) ? -1 : 1; 
        } 
  
        for(int i=0; i<n; i++){ 
            sum += a[i]; 
  
            if(sum == 0){ 
                max = i + 1; 
                end = i; 
            } 
  
            if(hM.containsKey(sum + n)){ 
                if(max < i - hM.get(sum + n)){ 
                    max = i - hM.get(sum + n); 
                    end = i; 
                } 
            } 
            else 
                hM.put(sum + n, i); 
        } 
  
        for(int i=0; i<n; i++) { 
            a[i] = (a[i] == -1) ? 0 : 1; 
        } 
  
        int index = end - max + 1; 
        
        if(end>-1)
            System.out.println(index + " to " + end); 
        else
            System.out.println("No such subarray"); 
        return max;  
    } 
    public static void main(String[] args){ 
        LongestSubArray s = new LongestSubArray(); 
        int a[] = { 1, 0, 1, 1, 1, 0, 0 }; 
        int n = a.length; 
        
        s.subArray(a, n); 
    } 
}
1 to 6

Аналіз складанасці

Складанасць часу

O (N) дзе n - колькасць элементаў у дадзеным масіве a []. Паколькі e выкарыстоўваецца unordered_map / HashMap, нам удалося дасягнуць O (N) часу, таму што HashMap дазваляе O (1) часу выконваць пошук па ўстаўцы, выдаленне.

Касмічная складанасць

O (N) таму што мы выкарыстоўвалі N дадатковага месца. Так як мы выкарыстоўвалі аб'яву HashMap, захоўвалася інфармацыя пра N элементаў, у горшым выпадку гэта можа быць N элементаў.