ყველაზე დიდი ქვეჯგუფი თანაბარი რაოდენობით 0s და 1s


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon Coursera რუხი ნარინჯისფერი MakeMyTrip Morgan Stanley Paytm ანოტაცია Times ინტერნეტი
Array Hash

გეძლევათ მთელი რიგის მთელი რიგი. მთელი რიცხვები შეყვანის მასივში მხოლოდ 0 და 1ა. პრობლემის დებულება ითხოვს, რომ გაირკვეს უდიდესი ქვე-მასივი, რომელსაც შეიძლება ჰქონდეს 0 და 1-ების ტოლი რაოდენობა.

მაგალითი

arr[]={0,1,0,1,0,1,1,1}
0 to 5 (total 6 elements)

განმარტება

მასივის პოზიციიდან 0-დან 5-მდე იყო 0-სა და 1-ის ტოლი არ

0-ების რაოდენობა 3

1-ების რაოდენობა ⇒ 3

ეს არის ყველაზე დიდი ქვე-მასივი, რომელსაც ტოლი არ აქვს 0 და 1.

ალგორითმი იპოვნეთ უდიდესი ქვედანაყოფი, თანაბარი რაოდენობით 0s და 1s

  1. გამოაცხადეთ ა HashMap.
  2. უცნობია თანხა, მაქსიმალური სიგრძე, დაწყების ინდექსი 0-მდე და endingIndex -1-მდე.
  3. მასივის გადაკვეთა და მასივის თითოეული ელემენტის განახლება -1 – ით, თუ ის უდრის 0 – ს.
  4. დაიწყეთ მარყუჟი 0-დან n-1-მდე (n არის მასივის სიგრძე).
    1. Arr [i] - ის თითოეული მნიშვნელობის დამატება ჯამში.
    2. შეამოწმეთ არის თუ არა ჯამი 0-ის ტოლი, თუ სიმართლეა,
      1. შემდეგ განაახლეთ მაქსიმალური სიგრძე როგორც i + 1, და endingIndex როგორც მე
    3. შეამოწმეთ, შეიცავს თუ არა რუკა ჯამს + n,
      1. შემდეგ განაახლეთ maxLength სიგრძე, როგორც მნიშვნელობა i - რუკა (ჯამი + n) რუქიდან და endingIndex, როგორც i.
    4. სხვას განათავსეთ ეს ჯამი + n რუკაზე.
  5. დაბეჭდვის endingIndex - maxLength + 1 და endingIndex.

განმარტება

მასივის გათვალისწინებით და ჩვენ გვთხოვენ გავერკვიოთ უდიდესი ქვე-მასივი, თანაბარი რაოდენობით 0 და 1. იპოვნეთ ქვე-მასივის დიაპაზონი ისე, რომ ის ყველაზე დიდი უნდა იყოს ყველა ქვე-მასივის ყველა სიგრძეს შორის, რომელიც ინახავს 0 და 1-ების თანაბარ რაოდენობას. ჩვენ ვიყენებთ HashMap შენახვისთვის მთელი რიცხვი ღირებულებები მასში. ჰაშინგი უზრუნველყოფს ეფექტურ მიდგომას და დროის უკეთეს სირთულეს. აიღე ღირებულებები თანხა, მაქსიმალური სიგრძე როგორც 0, მაშინ ჩვენ ვაპირებთ მისი განახლებას კოდში. ჩვენ გვექნება ერთი ცვლადი, რომელსაც ეწოდება endingIndex, ეს ინახავს დიაპაზონის ბოლო წერტილის მნიშვნელობას, სადაც უნდა იყოს ქვე-მასივის ბოლოების დიაპაზონის მაქსიმალური სიგრძე.

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

ჩვენ ვაპირებთ, შევაჯამოთ მასივის ყველა მნიშვნელობა და ვიპოვოთ, თუ ის უდრის 0-ს, თუ ტოლია უბრალოდ განაახლეთ მასივის maxLength და მასივის endingIndex. ჩვენ ვაყენებთ ჯამს + n რუკაში, თუ ის უკვე არ არსებობს, და თუ ის არსებობს, შეამოწმეთ ზოგიერთი პირობა, შემდეგ განაახლეთ maxLength და endingIndex მნიშვნელობა. დაბეჭდვა endingIndex - maxLength + 1 როგორც დიაპაზონის საწყისი წერტილი და endingIndex როგორც დიაპაზონის დასასრული წერტილი.

ყველაზე დიდი ქვეჯგუფი თანაბარი რაოდენობით 0s და 1s

კოდი

C ++ კოდი, რომ იპოვოთ უდიდესი ქვედანაყოფი, თანაბარი რაოდენობით 0 და 1

#include<iostream>
#include<unordered_map>

using namespace std;

int getLargestSubA(int arr[], int n)
{
    unordered_map<int, int> MAP;

    int sum = 0;
    int maxLength = 0;
    int endingIndex = -1;

    for (int i = 0; i < n; i++)
        arr[i] = (arr[i] == 0) ? -1 : 1;

    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
        if (sum == 0)
        {
            maxLength = i + 1;
            endingIndex = i;
        }
        if (MAP.find(sum + n) != MAP.end())
        {
            if (maxLength < i - MAP[sum + n])
            {
                maxLength = i - MAP[sum + n];
                endingIndex = i;
            }
        }
        else
            MAP[sum + n] = i;
    }
    cout<<endingIndex - maxLength + 1 <<" to " <<endingIndex;

    return maxLength;
}

int main()
{
    int arr[] = { 0,1,0,1,0,1,1,1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    getLargestSubA(arr, n);
    return 0;
}
0 to 5

განხორციელება ჯავაში, ყველაზე დიდი ქვეჯგუფის მოსაძებნად, თანაბარი რაოდენობით 0 და 1

import java.util.HashMap;

class LargestSubArrayWithEqual01
{
    public static int getLargestSubA(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int sum = 0;

        int maxLength = 0;
        int endingIndex = -1;

        for (int i = 0; i < n; i++)
        {
            arr[i] = (arr[i] == 0) ? -1 : 1;
        }

        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
            if (sum == 0)
            {
                maxLength = i + 1;
                endingIndex = i;
            }
            if (MAP.containsKey(sum + n))
            {
                if (maxLength < i - MAP.get(sum + n))
                {
                    maxLength = i - MAP.get(sum + n);
                    endingIndex = i;
                }
            }
            else
                MAP.put(sum + n, i);

        }
        int end = endingIndex - maxLength + 1;
        System.out.println(end + " to " + endingIndex);

        return maxLength;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {0,1,0,1,0,1,1,1};
        int n = arr.length;

        getLargestSubA(arr, n);
    }
}
0 to 5

სირთულის ანალიზი

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

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. აქ ჩვენ შეგვიძლია გადავწყვიტოთ ეს პრობლემა O (n) - ში, რადგან ჩვენ გამოვიყენეთ HashMap. იმის გამო, რომ HashMap– ს შეუძლია შეიტანოს, წაშალოს ან შეცვალოს ელემენტები O (1) დროის სირთულეში.

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

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. მას შემდეგ, რაც ელემენტთა რაოდენობა, რომელიც ჩასმული იქნება უარეს შემთხვევაში, ჰასმაპში იქნება მაქსიმუმ n. ეს ხაზოვანი სივრცის სირთულე მიიღწევა.