1 களின் எண்ணிக்கையைக் கொண்ட மிக நீளமான சுபரே 0 வி எண்ணிக்கையை விட ஒன்று அதிகம்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அக்சன்சர் அமேசான் டி.இ ஷா சாம்சங்
அணி ஹாஷ்

நாங்கள் ஒரு கொடுத்துள்ளோம் வரிசை முழு எண்களின். ஒரு வரிசையில் 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 க்கு சமமாக இருந்தால், வெளியீட்டு நீளத்தின் புதுப்பிப்பைப் பெறுகிறோமா என்று நாங்கள் தேடுவோம். கடைசியாக, அறிக்கை, புதிய வெளியீட்டு நீளத்தைப் பெற்றால், முந்தையதை தற்போதைய வெளியீட்டு நீளத்துடன் புதுப்பிக்க வேண்டும், மேலும் வெளியீட்டு நீளத்தை திருப்பித் தருகிறோம்.

நடைமுறைப்படுத்தல்

மிக நீண்ட சுபாரேவுக்கான சி ++ நிரல் 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 களின் எண்ணிக்கையை விட ஒன்று அதிகம்

நேர சிக்கலானது

ஓ (n) எங்கே “N”  என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.

விண்வெளி சிக்கலானது

ஓ (n) எங்கே “N”  என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.