1s ගණනය කිරීම සහිත දිගම සබ්රේ 0s ගණනට වඩා එකකි  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇක්සෙන්චර් ඇමේසන් ඩී ෂෝ Samsung ජංගම දුරකථන
අරා හැෂ්

අපි ලබා දී ඇත අරාව නිඛිලවල. අරාවෙහි 1 සහ 0 පමණක් අඩංගු වේ. ගැටළු ප්‍රකාශය මඟින් දිගම උප-අරාවෙහි දිග සොයා ගැනීමට අසයි, එය 1 හි ඉලක්කම් ප්‍රමාණයක් උප-අරාවෙහි 0 ගණන්වලට වඩා එකකි.

උදාහරණයක්  

ආදානය:

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

ප්රතිදාන:

5

පැහැදිලි කිරීම:

0 සිට 4 දක්වා දර්ශකය, {1, 0, 1, 1, 0}, තුනක් ඇත 1 සහ 0 XNUMX. 1 ට වඩා 0 හි තවත් එක් ගණනය කිරීමක් පමණි.

ආදානය:

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

ප්රතිදාන:

3

පැහැදිලි කිරීම:

0 සිට 2 දක්වා දර්ශකය, {1, 0, 1}, 1 සහ 0 1 ඇත. 0 ට වඩා XNUMX හි තවත් එක් ගණනය කිරීමක් පමණි.

ඇල්ගොරිතම  

  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-index වෙත යාවත්කාලීන කරන්න.
  4. ප්‍රතිදාන දිග ආපසු එවන්න.
මෙයද බලන්න
M පරාසය ටොගල් මෙහෙයුම් වලින් පසු ද්විමය අරාව

පැහැදිලි කිරීම  

අපි අ සිතියම. එම සිතියමෙහි, කොන්දේසිය සෑහීමකට පත්වේ නම්, එකතුවක වටිනාකම සහ දර්ශකයක වත්මන් වටිනාකම අපි ගබඩා කරන්නෙමු. විචල්යයන් දෙකක් ගෙන එකතුව 0 ලෙසත්, නිමැවුම් දිග 0 ලෙසත් සකසන්න. අරාව හරහා ගමන් කරන විට, අපි අරාවෙහි සෑම අංගයක්ම තෝරා ගනිමු, සහ අර [i] 0 ට ​​සමාන දැයි පරීක්ෂා කරන්න, එය සමාන බව සොයාගතහොත්, අපි එකතු කරන්නෙමු -1 සිට එකතුව දක්වා එය ගබඩා කර තබන්න, එසේ නොමැති නම් අප 0 ලෙස සොයාගෙන නොමැති නම්, අපි ධනාත්මක 1 එකතු කර එකතුවට ගබඩා කරමු.

එම negative ණ 1 හා ධනාත්මක 1 පිටුපස ඇති හේතුව නම්, අපි සියලු 0 ගේ -1 සිට මවාපාමින් ඒවා 1 සමඟ එකතු කරන්නෙමු, එවිට අපට සෑම විටම 0 ලැබෙනු ඇත. නමුත් අපි ධනාත්මක 1 ක් සඳහා පරික්ෂා කරන්නෙමු, එයින් ඇඟවෙන්නේ අපට තවත් 1 ක් ඇති බවත් ඉන් පසුව 0 ගණන් කළ යුතු බවත්ය.

අපි 1 ලෙස -0 ලෙස මවාපානවා නම්, අපි 1, 0, 1 ක් ගනිමු යැයි සිතමු, පළමු අංක 0 සමඟ එම 2 අපට ලැබෙනු ඇති අතර, තුන්වන අංකය සමඟ අපගේ තත්වය සපුරා ඇති බව අපට සොයාගත හැකිය. අපට 1 සහ 0 හි උප-පෙළක් ලැබී ඇත්තේ එක් අමතර ගණන 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”  යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.