მომიჯნავე მასივი


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon MakeMyTrip Morgan Stanley Paytm
ჰაშინგი მოცურების ფანჯარა

მოცემული ან მასივი შედგება მხოლოდ 0 და 1 რიცხვებისგან. ჩვენ უნდა ვიპოვოთ გრძელი მომიჯნავე ქვე-მასივის სიგრძე, რომელიც თანაბრად შედგება o და 1

მაგალითი

შეყვანის

arr = [0,1,0,1,0,0,1]

გამოყვანის

6

განმარტება

Ყველაზე გრძელი მომიჯნავე ქვე-მასივი აღინიშნება წითელი [0,1,0,1,0,0,1] და მისი სიგრძეა 6.

ალგორითმი

  1. დააყენეთ მაქსილენის მნიშვნელობა 0-ზე.
  2. გამოიყენეთ ორი მარყუჟი, პირველ მარყუჟში დააყენეთ zer_count 0, one_count 0.
  3. თუ მნიშვნელობა მასივი კონკრეტულ ინდექსში აღმოჩნდა 0, შემდეგ გაზარდეთ ნულოვანი_ 1-ით.
  4. სხვა შემთხვევაში განაახლეთ და გაზარდეთ one_count 1-ით.
  5. თითოეულ გამეორებაზე შეამოწმეთ არის თუ არა ნულოვანი ანგარიში ტოლი ერთი_თვლა, თუ ტოლია, შემდეგ გაარკვიეთ, თუ რა არის მეტი (maxlen და j-i + 1)
  6. დაბრუნება maxlen

განმარტება

ჩვენი მთავარი იდეა არის გრძელი მომიჯნავე ქვეჯგუფის სიგრძის პოვნა, რომელსაც აქვს ნულოვანი და მხოლოდ ერთი, ამიტომ ჩვენი მთავარი მიზანი არის ამ სიგრძის პოვნა.

ამიტომ, ჩვენ ვაპირებთ გამოვიყენოთ მარყუჟისთვის ჩასმული. გარე მარყუჟში, ჩვენ ვიწყებთ ნულოვანი_ანგარიშის მნიშვნელობას და ერთი_ანგარიშს 0-მდე, რადგან ყოველი განმეორების შემდეგ, როდესაც იგი გამოვა შიდა ციკლიდან, ჩვენ გვჭირდება ნულოვანი_ანგარიშის და ერთი_ანგარიშის ახალი მნიშვნელობები, რომ თავიდან გადავამოწმოთ იგი. ჩვენ ვაპირებთ განმეორებით მარყუჟს, სანამ მასივის სიგრძე არ მიიღწევა.

ახლა იგი შეამოწმებს მასივის თითოეულ მნიშვნელობას, თუ arr [index] - ს აქვს 0 ან 1 მნიშვნელობა, თუ მას აქვს 0-ის ტოლი მნიშვნელობა, განაახლეთ და გაზარდეთ ნულოვანი_ანგარიშის მნიშვნელობა 1-ით ან თუ arr- ის მნიშვნელობა [ინდექსი] აღმოჩნდა, რომ არის 1, შემდეგ იგი განახლდება და ზრდის ერთი_ანგარიშის მნიშვნელობას 1-ით.

ახლა, შემდეგი ბლოკი აპირებს შეამოწმოს არის თუ არა ნულოვანი_სთვლა ტოლია ერთი_თვლა, თუ ტოლია, შემდეგ გაარკვიეთ, თუ რომელია მეტი რიცხვი მაქსლენს და j-i + 1-ს შორის და უფრო მეტ რიცხვს ინახავს მაქსილენში.

მაგალითი

დავუშვათ, მოცემულია მასივი: arr [] = {1,0,0,1,0,1,0}

zero_count = 0, one_count = 0, maxlen = 0

i = 0, => j = i

j = 0

arr [j] - ზე ტოლი არ არის 0, მაშინ one_count ++, ნიშნავს one_count = 1

j = 1

Arr [j] - ზე ტოლია 0, მაშინ zero_count ++, ნიშნავს zero_count = 1

ამ ადგილას შემდეგ, თუ ბლოკი შესრულდება, ის უფრო მეტ მნიშვნელობას არ ანიჭებს maxlen- ს და j-i + 1-ს და უბრუნებს 2-ს maxlen- ში

j = 2

Arr [j] - ზე ტოლია 0, მაშინ zero_count ++, ნიშნავს zero_count = 2

j = 3

Arr [j] - ზე ტოლი არ არის 0, მაშინ one_count ++, ნიშნავს one_count = 2

ამ ადგილას შემდეგ, თუ ბლოკი შესრულდება, ის უფრო მეტ მნიშვნელობას არ ანიჭებს maxlen- ს და j-i + 1- ს და უბრუნებს 4-ს maxlen- ში.

j = 4

Arr [j] - ზე ტოლია 0, მაშინ zero_count ++, ნიშნავს zero_count = 3

j = 5

Arr [j] - ზე ტოლი არ არის 0, მაშინ one_count ++, ნიშნავს one_count = 3

ამ ადგილას შემდეგ, თუ ბლოკი შესრულდება, ის უფრო მეტ მნიშვნელობას არ ანიჭებს maxlen- ს და j-i + 1- ს და უბრუნებს 6-ს maxlen- ში.

j = 6

Arr [j] - ზე ტოლია 0, მაშინ zero_count ++, ნიშნავს zero_count = 4

და ის განაგრძობს მარყუჟის განმეორებას, სანამ ყველა პირობა ვერ მოხერხდება.

და მაქსლენის დაბრუნება 6-ით.

განხორციელება

C ++ პროგრამა მომიჯნავე მასივისთვის

#include <iostream>
using namespace std;
int contiguous_Array(int arr[], int n)
{
    int i,j,maxlen=0;
    for( i = 0 ; i < n ; i++)
    {
        int zero_count=0,one_count=0;
        for(j = i ; j < n ; j++)
        {
            if( arr[j] == 0 )
            {
                zero_count++;
            }
            else
            {
                one_count++;
            }
            if(zero_count==one_count)
            {
                maxlen=std::max(maxlen,j-i+1);
            }
        }
    }
    return maxlen;
}
int main()
{
    int arr[]= {1,0,0,1,0,1,0};
    int n=sizeof(arr)/sizeof(arr[0]);
    cout <<contiguous_Array(arr,n)<< endl;
    return 0;
}
6

Java პროგრამა მომიჯნავე მასივისთვის

public class Contiguous_Array {

  public static int solution(int[] arr) {

    int maxlen = 0;

    for (int i = 0; i<arr.length; i++) {

      int zero_count = 0, one_count = 0;

      for (int j = i; j<arr.length; j++) {

        if (arr[j] == 0) {
          zero_count++;
        } else {
          one_count++;
        }
        if (zero_count == one_count) {

          maxlen = Math.max(maxlen, j - i + 1);

        }
      }
    }
    return maxlen;
  }
  public static void main(String args[]) {

    int[] arr = new int[] {
      0, 1, 0, 1, 0, 0, 1
    };

    System.out.println(solution(arr));

  }
}
6

სირთულის ანალიზი მომიჯნავე მასივისთვის

დროის სირთულე

O (N * N) სადაც N მოცემული მასივის ზომაა.

სივრცის სირთულე

O (1) რადგან აქ დამატებით ადგილს არ ვიყენებთ.

Reference