બહુમતી એલિમેન્ટ II લીટકોડ સોલ્યુશન


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન બ્લૂમબર્ગ ફેસબુક Google માઈક્રોસોફ્ટ Zenefits
અરે

આ સમસ્યામાં, અમને એક આપવામાં આવે છે એરે પૂર્ણાંકોની. ધ્યેય એ છે કે જે બધા તત્વો કરતાં વધુ થાય શોધવા માટે છે /N / 3⌋ એરેનો સમય જ્યાં એરેનો N = કદ અને ⌊. ફ્લોર ઓપરેટર છે. આપણે આવા તત્વોની એરે પરત કરવાની જરૂર છે.

તત્વોની શ્રેણી: -10 ^ 9 થી 10 ^ 9

ઉદાહરણ

Array = {1 , 2 , 3 , 3 , 2}
2 3

સમજૂતી⌊N / 3⌋ = ⌊5 / 3⌋ = 1. હવે, પૂર્ણાંકો 2 અને 3 ની ફ્રીક્વન્સીઝ 2 ની બરાબર હોય છે, જે વધારે છે. તેથી, અમે તેને છાપીશું.

Array = {1 , 2 , 3 , 4}
No majority elements

સમજૂતી: અમને આ કિસ્સામાં કોઈ તત્વ મળ્યું નથી, જેની આવર્તન 1 કરતા વધારે હોય. તેથી, આપણે "મોટા ભાગના તત્વો નથી" છાપીશું.

અભિગમ (સંગ્રહિત આવર્તન)

શીર્ષક સૂચવે છે તેમ, આપણે હેશ ટેબલનો ઉપયોગ કરીને એરેમાં દરેક તત્વની આવર્તન સંગ્રહિત કરી શકીએ છીએ અને પછી આવર્તન કરતા વધારે તત્વો તપાસી શકીએ છીએ. /N / 3⌋. આ રીતે, આપણે એવા બધા તત્વો શોધી શકીએ છીએ જે સ્થિતિને સંતોષે છે.

અલ્ગોરિધમ

  1. હેશમેપ શરૂ કરો-આવર્તન એરેમાં તત્વોની આવર્તન અને સૂચિ / વેક્ટર સંગ્રહિત કરવા પરિણામ બહુમતી તત્વો સંગ્રહવા માટે
  2. દરેક તત્વ માટે એરેમાં:
    • તેની આવર્તન વધારો: આવર્તન [i] ++ (અથવા પહેલેથી હાજર ન હોય તો 1 તરીકે સેટ કરો)
  3. બધા માટે કી હેશમેપમાં:
    1. If આવર્તન [કી] > એન / 3
      1. તેને ઉમેરો પરિણામ
  4. સૂચિ પરત કરો પરિણામ

બહુમતી એલિમેન્ટ II લીટકોડ સોલ્યુશનનો અમલ

સી ++ પ્રોગ્રામ

#include <bits/stdc++.h>
using namespace std;

vector<int> majorityElement(vector<int>& a)
{
    int N = a.size();
    vector <int> result;
    unordered_map <int , int> frequency;
    for(int &x : a)
        frequency[x]++;
    for(auto &x : frequency)
        if(x.second > N / 3)
            result.emplace_back(x.first);
    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 3 , 3 , 2};
    vector <int> result = majorityElement(a);
    if(result.empty())
        cout << "No majority elements\n";
    else
        for(int &x : result)
            cout << x << " ";
    return 0;
}

જાવા પ્રોગ્રામ

import java.util.*;

class majority_element_ii
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 3 , 3 , 2};
        List <Integer> result = majorityElement(a);
        if(result.size() == 0)
            System.out.println("No majority elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> majorityElement(int[] a)
    {
        List <Integer> result = new ArrayList <Integer>();
        HashMap <Integer , Integer> frequency = new HashMap <>();

        for(int i = 0 ; i < a.length ; i++)
            frequency.put(a[i] , frequency.getOrDefault(a[i] , 0) + 1);

        for(Map.Entry i : frequency.entrySet())
        {
            Integer value = (int)i.getValue() , key = (int)i.getKey();
            if((int)value > ((a.length) / 3))
                result.add(key);
        }
        return result;
    }
}
2 3

બહુમતી એલિમેન્ટ II લીટકોડ સોલ્યુશનનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) આપણે ફ્રીક્વન્સીઝને અપડેટ કરવા માટે એકવાર આખા એરેને પસાર કરીએ છીએ. N એરેનું = કદ.

અવકાશ જટિલતા

ઓ (એન) જેમ કે ફ્રીક્વન્સીઝ સ્ટોર કરવા માટે આપણે હેશ ટેબલનો ઉપયોગ કરીએ છીએ.

અભિગમ (બોયર-મૂર મતદાન એલ્ગોરિધમ)

અહીં નોંધવાની પ્રથમ વસ્તુ એ છે કે ત્યાં આવર્તન સાથે મહત્તમ 2 તત્વો હોઈ શકે છે RayN / 3⌋ એરેમાં. તેથી, આ સમસ્યા જેવું જ બને છે બહુમતી તત્વ સાથે સમસ્યા 2 બહુમતી તત્વો આ વખતે.

બાયર-મૂરના મતદાન અલ્ગોરિધમનો ઉપયોગ કરીને અમે પહેલાથી જ બહુમતી ઘટકની સમસ્યા હલ કરી દીધી છે. એકલ બહુમતી તત્વના કિસ્સામાં, આપણે વર્તમાન તત્વ ઉમેદવાર છે કે નહીં તેની તુલના કરીને એલ્ગોરિધમનો ઉપયોગ કરી શકીએ. પરંતુ, આ કિસ્સામાં, આપણે બે સંભવિત બહુમતી તત્વો ધરાવવાની અને તેમના કાઉન્ટર્સને સમાંતર અપડેટ કરવાની જરૂર છે. આ અંતર્જ્itionાનની સહાયથી, આપણે આપણી શરતો નીચે મુજબ સેટ કરી શકીએ છીએ.

  • એરેમાં તત્વોની શ્રેણીની બહાર કોઈપણ બે રેન્ડમ ઉમેદવારોને સેટ કરો.
  • જો તત્વ કોઈપણ ઉમેદવારની બરાબર હોય, તો તેના કાઉન્ટરમાં વધારો.
  • જો એક ઉમેદવારનો કાઉન્ટર બરાબર છે 0 કોઈપણ બિંદુએ, અમે વર્તમાન તત્વને ઉમેદવાર તરીકે સેટ કરીએ છીએ if આ વર્તમાન તત્વ અન્ય ઉમેદવાર નથી.
  • જો વર્તમાન તત્વ કોઈપણ ઉમેદવારની બરાબર ન હોય તો અમે બંને ઉમેદવારોના કાઉન્ટરો ઘટાડીએ છીએ.

આ રીતે, અમે પહેલા ઉમેદવાર બીજાને અસર કર્યા વિના, એરેમાં બે અલગ અલગ ઉમેદવારોને સમાંતર જાળવી રાખીએ છીએ. જો કે, આ શક્ય છે કે આપણે જે ઉમેદવારો સાથે અંત કરીયે તે સાચા બહુમતી તત્વો ન હોય ({1, 1, 2, 2, 3, 3 such એનું એક ઉદાહરણ છે). તેથી, આપણે સમાપ્ત થતા ઉમેદવારોની આવર્તનની ગણતરી માટે બીજો પાસ ચલાવવો જરૂરી છે. તેના આધારે, અમે બહુમતી તત્વોના વેક્ટરને પરત આપી શકીએ છીએ.

અલ્ગોરિધમ

  1. પ્રારંભ કરો કેન્ડઓન અને મીણબત્તી બે ઉમેદવારો અને તેમની આવર્તન સંગ્રહિત કરવા cntOne અને cntTwo as 0.
  2. દરેક તત્વ માટે એરેમાં:
    • If કેન્ડઓન == હું:
      • cntOne++
    • અન્યથા જો ક candન્ડટવ == i
      • cntTwo++
    • અન્યથા જો સી.એન.એક == 0
      • સોંપો i as કેન્ડઓન: કેન્ડઓન = i
      • તેની ગણતરી 1 તરીકે સેટ કરો: cntOne = 1
    • અન્યથા જો cntTwo == 0
      • કેન્ડટવો = i
      • cntTwo = 1
    • બંને ઉમેદવારોની ઘટતી સંખ્યા:
      • cntOne–
      • cntTwo–
  3. બીજા પાસ માટે શૂન્ય પર તેમની ગણતરીઓ ફરીથી સેટ કરો: cntOne = 0 અને cntTwo = 0
  4. એરેમાં દરેક તત્વ માટે:
    • જો તે કેન્ડઓન સમાન છે:
      • cntOne ++
    • અન્યથા જો તે મીણબત્તી બરાબર છે:
      • cntTwo ++
  5. સૂચિ / વેક્ટર પ્રારંભ કરો પરિણામ બહુમતી તત્વો સંગ્રહવા માટે
  6. જો સી.ટી.ઓન> એન / 3
    • દબાણ કરો કેન્ડઓન થી પરિણામ
  7. જો cntTwo> એન / 3
    • દબાણ કરો ક candન્ડટવ થી પરિણામ
  8. પરિણામ છાપો

ઉદાહરણ:

બહુમતી એલિમેન્ટ II લીટકોડ સોલ્યુશન

બહુમતી એલિમેન્ટ II લીટકોડ સોલ્યુશનનો અમલ

સી ++ પ્રોગ્રામ

#include <bits/stdc++.h>
using namespace std;

vector <int> majorityElement(vector <int> &a)
{
    vector <int> result;
    int candOne = (int)1e9 + 1 , candTwo = (int)1e9 + 1 , cntOne = 0 , cntTwo = 0;
    for(int &i : a)
    {
        if(candOne == i)
            cntOne++;
        else if(candTwo == i)
            cntTwo++;
        else if(cntOne == 0)
        {
            candOne = i;
            cntOne++;
        }
        else if(cntTwo == 0)
        {
            candTwo = i;
            cntTwo++;
        }
        else
        {
            cntOne--;
            cntTwo--;
        }
    }

    cntOne = 0;
    cntTwo = 0;
    for(int &i : a)
    {
        if(i == candOne)
            cntOne++;
        if(i == candTwo)
            cntTwo++;
    }

    if(cntOne > ((int)a.size()) / 3)
        result.push_back(candOne);
    if(cntTwo > ((int)a.size()) / 3)
        result.push_back(candTwo);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 3 , 3 , 2};
    vector <int> result = majorityElement(a);
    if(result.empty())
        cout << "No majority elements\n";
    else
        for(int &x : result)
            cout << x << " ";
    return 0;
}

જાવા પ્રોગ્રામ

import java.util.*;

class majority_element_ii
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 3 , 3 , 2};
        List <Integer> result = majorityElement(a);
        if(result.size() == 0)
            System.out.println("No majority elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> majorityElement(int[] a)
    {
        List <Integer> result = new ArrayList<>();

        int candOne = (int)1e9 + 1 , candTwo = (int)1e9 + 1 , cntOne = 0 , cntTwo = 0;
        for(int i : a)
        {
            if(candOne == i)
                cntOne++;
            else if(candTwo == i)
                cntTwo++;
            else if(cntOne == 0)
            {
                candOne = i;
                cntOne++;
            }
            else if(cntTwo == 0)
            {
                candTwo = i;
                cntTwo++;
            }
            else
            {
                cntOne--;
                cntTwo--;
            }
        }

        cntOne = 0;
        cntTwo = 0;
        for(int i : a)
        {
            if(i == candOne)
                cntOne++;
            if(i == candTwo)
                cntTwo++;
        }

        if(cntOne > (a.length) / 3)
            result.add(candOne);
        if(cntTwo > (a.length) / 3)
            result.add(candTwo);

        return result;
    }
}
3 2

બહુમતી એલિમેન્ટ II લીટકોડ સોલ્યુશનનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) આપણે ઇનપુટને ધ્યાનમાં લીધા વગર એરેના બે પાસ ચલાવીશું. N એરેનું = કદ.

અવકાશ જટિલતા

ઓ (1) જેમ આપણે સતત મેમરી સ્પેસ.