سب سے طویل سببری 1s کی گنتی سے کہیں زیادہ 0s کی گنتی والا ہے


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایکسینچر ایمیزون ڈی ای شا سیمسنگ
لڑی ہیش

ہم نے ایک دیا ہے صف عدد کا ایک صف میں صرف 1 اور 0 ہے۔ مسئلے کے بیان میں سب سے طویل ذیلی صف کی لمبائی معلوم کرنے کے لئے کہا گیا ہے جس میں 1 کے ہندسے کی مقدار ہونا ایک ذیلی صف میں 0 کی گنتی سے صرف ایک اور ہے۔

مثال کے طور پر

ان پٹ:

ارر [] = {1,0,1,1,0,0,0،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

: پیداوار

5

وضاحت:

0 سے 4 انڈیکس ، {1 ، 0 ، 1 ، 1 ، 0} میں ، تین ہیں 1 اور دو 0's. 1 کی نسبت 0 کی XNUMX کی ایک اور گنتی۔

ان پٹ:

ارر [] = {1,0,1,0,0،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

: پیداوار

3

وضاحت:

0 سے 2 انڈیکس ، {1 ، 0 ، 1} میں ، دو 1 اور ایک 0 ہیں۔ 1 کی نسبت 0 کی XNUMX کی ایک اور گنتی۔

الگورتھم

  1. نقشہ کا اعلان کریں۔
  2. جوڑ اور آؤٹ پٹ لمبائی کو 0 پر سیٹ کریں۔
  3. صف کو عبور کریں ، جبکہ i = 0 سے i <n۔
    1. چیک کریں کہ آیا آرر [i] 0 کے برابر ہے اگر صحیح ہے تو -1 کو جوڑنے میں شامل کریں۔
    2. بصورت دیگر 1 + کا اضافہ کریں۔
    3. چیک کریں اگر رقم برابر ہے 1 میں ، پھر آؤٹ پٹ لمبائی کی قدر میں 1 اضافہ کریں۔
    4. دوسری صورت میں ، چیک کریں کہ اگر کسی نقشہ میں وہ رقم نہیں ہے جو صحیح ہے تو پھر نقشہ میں i کی رقم اور حالیہ قیمت کو ساتھ ساتھ جوڑ دیں۔
    5. چیک کریں کہ آیا کسی نقشہ میں (جمع 1) شامل ہے۔
    6. اگر آؤٹ پٹ لمبائی آئی انڈیکس سے کم ہے (نقشہ میں مجموعی قیمت)
      1. اگر سچ ہے تو ، پھر آؤٹ پٹ لمبائی کو آئی انڈیکس میں تازہ کریں۔
  4. آؤٹ پٹ کی لمبائی واپس کریں۔

وضاحت

ہم اعلان کریں گے a نقشہ. اس نقشے میں ، اگر شرط مطمئن ہوجائے تو ہم رقم کی قیمت اور انڈیکس کی موجودہ قیمت کو ذخیرہ کرنے جارہے ہیں۔ دو متغیر لیں اور 0 اور آؤٹ پٹ لمبائی سے 0 کی رقم مقرر کریں ، جب صف میں سے گزرتے ہوئے ، ہم کسی صف کے ہر عنصر کو چنیں گے ، اور اگر جانچ پڑتال کریں گے کہ اگر [i] 0 کے برابر ہے تو ، اگر وہ برابر پایا جاتا ہے ، تو ہم اس میں اضافہ کریں گے۔ -1 کا خلاصہ اور اسے ذخیرہ کرنے کے ل. ، بصورت دیگر اگر ہم 0 نہیں پاسکتے ہیں تو ، ہم اس میں 1 مثبت رقم کا اضافہ کریں گے اور اسے ذخیرہ کرنے کے لئے ذخیرہ کریں گے۔

اس منفی 1 اور مثبت 1 کے پیچھے کی وجہ یہ ہے کہ ، ہم سب 0 سے -1 کا دکھاوا کر رہے ہیں اور انہیں 1 کے ساتھ شامل کرتے ہیں ، لہذا ہمیں ہمیشہ 0 ملے گا۔ لیکن ہم مجموعی طور پر مثبت 1 کی جانچ کریں گے ، جو اس بات کی نشاندہی کرتا ہے کہ ہمارے پاس ایک اضافی 1 ہوگا پھر 0 کی گنتی۔

فرض کیج we ، ہم 1 ، 0 ، 1 لیں گے اگر ہم 0 کو بطور -1 دکھاوا کر رہے ہیں ، تو ہمیں 0 ملے گا پہلے 2 نمبر کے ساتھ ، اور تیسرے نمبر کے ساتھ ، ہم یہ پائیں گے کہ ہماری حالت پوری ہوگئی ہے۔ ہمیں 1 سے 0 کی ایک اضافی گنتی کے ساتھ 1 اور 0's کی ذیلی سرنی مل گئی۔ اسی وجہ سے ہم تلاش کریں گے کہ اگر الگورتھم کے اگلے مرحلے میں رقم 1 کے برابر ہے اور آؤٹ پٹ لمبائی کی لمبائی کو اپ ڈیٹ کیا جائے گا۔ آخر میں ، اگر بیان ، اگر ہمیں نئی ​​آؤٹ پٹ کی لمبائی مل جاتی ہے تو ، ہمیں موجودہ آؤٹ پٹ لمبائی کے ساتھ پچھلی ایک کو اپ ڈیٹ کرنے کی ضرورت ہے اور ہم آؤٹ پٹ لینتھ کو واپس کردیں گے۔

عمل

سب سے طویل سببریے کے لئے C ++ پروگرام جس میں 1s کی گنتی 0s کی گنتی سے کہیں زیادہ ہے

#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

سب سے طویل سبابرے کے لئے جاوا پروگرام جس میں 1s کی گنتی 0s کی گنتی سے کہیں زیادہ ہے

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

1s کی گنتی 0s کی گنتی سے کہیں زیادہ طویل سببری کے لئے پیچیدہ تجزیہ

وقت کی پیچیدگی

اے (ن) کہاں "این"  صف میں عناصر کی تعداد ہے۔

خلائی پیچیدگی

اے (ن) کہاں "این"  صف میں عناصر کی تعداد ہے۔