ترټولو اوږد سببي د 1s شمیر څخه ډیر د 0s حساب لري  


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي Accenture ترلاسه کړئ Amazon DE شا سامسنګ
پیشه هاش

موږ ورکړل سور د عدد شمیره. یو صف یوازې 1 او 0 لري. د ستونزې بیان غوښتنه کوي ترڅو د اوږدې فرعي سرې اوږدوالی ومومي کوم چې د 1 عددي مقدار درلودل په فرعي صف کې د 0's شمیرو څخه یو څه ډیر دی.

بېلګه  

تفتیش:

تیر [] = {1,0,1,1,0,0,0،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

محصول:

5

وضاحت:

له 0 څخه تر 4 شاخص پورې ، {1 ، 0 ، 1 ، 1 ، 0} ، درې شتون لري 1's او دوه 0's. د 1's څخه د 0's یوازې یو بل شمیرنه.

تفتیش:

تیر [] = {1,0,1,0,0،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

محصول:

3

وضاحت:

له 0 څخه 2 شاخصونو کې ، {1 ، 0 ، 1} ، دوه 1's او یو 0 دی. د 1's څخه د 0's یوازې یو بل شمیرنه.

الګوریتم  

  1. نخشه اعلان کړئ.
  2. شمیره او وتنه لمبر یې تر 0 پورې تنظیم کړئ.
  3. صف ته ځیر شئ ، پداسې حال کې چې i = 0 تر i <n.
    1. وګوره که آرر [i] د 0 سره مساوي وي که ریښتیا وي بیا بیا بیا جمع کولو ته -1 اضافه کړئ.
    2. او یا هم د لنډون لپاره +1 اضافه کړئ.
    3. وګوره که جمع مساوي ده تر 1 پورې ، بیا د 1 لخوا د आउटपुट اوږدوالي ارزښت لوړ کړئ.
    4. بل ، چیک کړئ چې که نقشه کې مجموعه نه وي نو که ریښتیا وي نو بیا د i ټولیز او اوسنی ارزښت د لنډیز سره نقشه ته واچوئ.
    5. وګورۍ که نقشه کې (جمع 1) شتون لري.
    6. که آؤټ پټ لمینټ د آی - انډیکس څخه لږ وي (په نقشه کې مجموعه ارزښت).
      1. که ریښتیا وي ، نو بیا انلاینټ انټرنیټ ته i - شاخص ته تازه کړئ.
  4. د وتنې اوږدوالی راستون کړئ.
هم وګوره
بائنری صف د ټیګونو د عملیاتو د حد څخه وروسته

تشریح  

موږ به اعالن کړو نقشه. پدې نقشه کې ، موږ د پیسو ارزښت او د شاخص اوسنی ارزښت ذخیره کوو ، که چیرې حالت خوښ شي. دوه تغیرات واخلئ او 0 ته ټیټ او آوټینټ اوږدوالی تر 0 پورې تنظیم کړئ ، پداسې حال کې چې د صفونو تعقیب ، موږ به د یو سرلیک عنصر غوره کړو ، او وګورو چې آرر [i] د 0 سره مساوي وي ، که چیرې دا مساوي وموندل شي ، نو موږ به یې اضافه کړو -1 جمع کولو لپاره او د دې ذخیره کولو لپاره یې ذخیره کړئ ، که نه نو موږ 0 ونه موندله ، نو موږ به مثبت 1 اضافه کړو چې دا یې لنډ او ذخیره کړو.

د دې منفي 1 او مثبت 1 ترشا دلیل دا دی ، موږ د 0 1 ټول ټکي ښکار کوو او د 1 سره یې اضافه کوو ، نو موږ به 0 تل ترلاسه کړو. مګر موږ به په مجموع کې د مثبت 1 لپاره وګورو ، کوم چې په ګوته کوي چې موږ به یو اضافي 1 ولرو بیا د 0's شمیره.

فرض کړئ ، موږ به 1 ، 0 ، 1 واخلو که چیرې موږ 0 لکه -1 وړاندې کوو ، نو موږ به 0 د لومړي 2 شمیرو سره ترلاسه کړو ، او د دریمې شمیرو سره ، موږ موندلی شو چې زموږ حالت بشپړ شوی. موږ د 1 او 0's فرعي سرې ترلاسه کړې د 1 په پرتله د 0 اضافي شمیرو سره. موږ خپل حالت راضي کوو. له همدې امله موږ به په لټه کې شو که چیرې جمع د الګوریتم په بل مرحله کې 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 ډیر شمیر لري  

د وخت پیچلتیا

اې (N) هلته "n"  په صف کې د عناصرو شمیر دی.

د ځای پیچلتیا

اې (N) هلته "n"  په صف کې د عناصرو شمیر دی.