გრძელი ქვეჯგუფის რიცხვი 1-ები ერთით მეტი ვიდრე 0-ების რაოდენობა


Რთული ტური Easy
ხშირად ეკითხებიან Accenture Amazon დე შოუ Samsung
Array Hash

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

მაგალითი

შეყვანის:

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

გამოყვანის:

5

განმარტება:

0-დან 4 ინდექსამდე, {1, 0, 1, 1, 0}, არის სამი 1 და ორი 0. 1-ის მხოლოდ ერთი დათვლა, ვიდრე 0-ის.

შეყვანის:

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

გამოყვანის:

3

განმარტება:

0-დან 2-მდე ინდექსში, {1, 0, 1}, არის ორი 1 და ერთი 0. 1-ის მხოლოდ ერთი დათვლა, ვიდრე 0-ის.

ალგორითმი

  1. რუქის გამოცხადება.
  2. დააყენეთ ჯამი და გამომავალი სიგრძე 0-ზე.
  3. მასივის გადაკვეთა, ხოლო i = 0 - დან i <n.
    1. შეამოწმეთ არის თუ არა arr [i] ტოლი 0-ის, თუ სიმართლეა, შემდეგ დაამატოთ -1 ჯამი.
    2. სხვა ჯამში დაამატე +1.
    3. შეამოწმეთ თუ არა ჯამი ტოლია 1-მდე, შემდეგ გაზრდის გამომავალი მნიშვნელობის სიგრძე 1-ით.
    4. სხვაგვარად, შეამოწმეთ, თუ რუკა არ შეიცავს ჯამს, თუ სიმართლეა, მაშინ ჯამთან ერთად განათავსეთ i- ს ჯამი და მიმდინარე მნიშვნელობა.
    5. შეამოწმეთ, შეიცავს თუ არა რუქა (ჯამი -1).
    6. თუ გამომავალი სიგრძე ნაკლებია i- ინდექსზე (ჯამი არის მნიშვნელობა რუკაზე).
      1. თუ სიმართლეა, მაშინ განაახლეთ გამომავალი სიგრძე i- ინდექსამდე.
  4. დააბრუნეთ გამომავალი სიგრძე.

განმარტება

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

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

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

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

C ++ პროგრამა გრძელი ქვეჯგუფისთვის, რომელსაც აქვს 1-ების რაოდენობა, ერთი-ზე მეტი, ვიდრე 0-ების რაოდენობა

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}
Length of the longest Sub-Array : 5

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

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

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

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}
Length of the longest Sub-Array : 5

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

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

O (n) სადაც "ნ"  არის მასივის ელემენტების რაოდენობა.

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

O (n) სადაც "ნ"  არის მასივის ელემენტების რაოდენობა.