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


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન Atlassian બ્લૂમબર્ગ ફેસબુક GoDaddy Google માઈક્રોસોફ્ટ ઓરેકલ કલમ Snapchat યાહૂ Zenefits
વિભાજીત અને વિજય હેશિંગ

સમસ્યા નિવેદન

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

ઉદાહરણ

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

સમર્પણ: ⌊N / 2⌋ = 4/2 = 2. અને પૂર્ણાંક '3' એરેમાં 3 વખત થાય છે.

Array = {1 , 1 , 2}
1

સમજૂતી: ⌊N / 2⌋ = ⌊3 / 2⌋ = 1. અને '1' એરેમાં 2 વખત થાય છે.

અભિગમ (હેશટેબલ)

આપણે એશમાં દરેક એલિમેન્ટની આવર્તનને હેશ ટેબલમાં સ્ટોર કરી શકીએ છીએ. પછી આવર્તન> ⌊N / 2⌋ ધરાવતા પૂર્ણાંકની તપાસ કરવી સરળ બને છે.

અલ્ગોરિધમ

  1. એરેમાં પૂર્ણાંકોની આવર્તન સંગ્રહવા માટે હેશ ટેબલનો પ્રારંભ કરો: આવર્તન
  2. દરેક તત્વ માટે, i, એરેમાં:
    • વધારો આવર્તન [i] અથવા સેટ કરો આવર્તન [i] = 0 જો તે પહેલેથી જ કોષ્ટકમાં નથી
    •  If આવર્તન [i] > એન / 2:
      • પરત i
  3. રીટર્ન -1 (સંકલન ભૂલને ટાળવા માટે)
  4. પરિણામ છાપો

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

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

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

int majorityElement(vector <int> &a)
{
    int majorityCount = ((int) a.size()) / 2;
    unordered_map <int , int> frequency;
    for(int &i : a)
    {
        if(++frequency[i] > majorityCount)
            return i;
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
    cout << majorityElement(a) << '\n';
    return 0;
}

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

import java.util.*;

class majority_element
{
    public static void main(String args[])
    {
        int[] a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
        System.out.println(majorityElement(a));
    }

    static int majorityElement(int[] a)
    {
        HashMap <Integer , Integer> frequency = new HashMap<>();
        for(int i = 0 ; i < a.length ; i++)
        {
            frequency.put(a[i] , frequency.getOrDefault(a[i] , 0) + 1);
            if(frequency.get(a[i]) > a.length / 2)
                return a[i];
        }
        return -1;
    }
}
2

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

સમય જટિલતા

ઓ (એન) બહુમતી તત્વ શોધવા માટે આપણે એક વાર એરેને પસાર કરીએ છીએ. N એરેનું = કદ.

અવકાશ જટિલતા

ઓ (એન) કારણ કે એરેમાં વિશિષ્ટ તત્વોની મહત્તમ સંખ્યા હોઈ શકે છે: એન - ⌊N / 2⌋ કારણ કે બહુમતી તત્વ ઓછામાં ઓછો કબજો કરે છે /N / 2⌋ સૂચકાંકો. તેથી, જગ્યાની જટિલતા રેખીય છે.

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

આ સમસ્યા એ તત્વોના પ્રવાહમાં બહુમતી તત્વ કેવી રીતે શોધી શકાય છે તેનું સરસ ઉદાહરણ છે. બોયર-મૂર મતદાન ગાણિતીક નિયમોનો ક્રમ ⌊N / 2⌋ કરતા વધારે સ્થાનો ધરાવતા તત્વને શોધવા માટે વપરાય છે. આ અલ્ગોરિધમનો જાળવણી એ ઉમેદવાર અને તેના ગણતરી એરે માં. અમે સાથે એરેનો એક પાસ ચલાવો ઉમેદવાર = -1 અને ગણતરી = 0. જો એરેમાં કોઈપણ તત્વ છે ઉમેદવાર, અમે વધારો ગણતરી. નહિંતર, અમે તેને ઘટાડીએ છીએ. જો ગણતરી શૂન્ય થઈ જાય, તો આપણે બદલીએ ઉમેદવાર અને સુયોજિત કરો ગણતરી 0 પર પાછા.

તેની કામગીરીને સમજવા માટે, નીચેના ઉદાહરણને અનુસરો:

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

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

અલ્ગોરિધમ

  1. બે ચલો પ્રારંભ કરો: ઉમેદવાર અને CNT ઉમેદવાર અને સંબંધિત આવર્તન માટે તેની આવર્તન સંગ્રહિત કરવા
  2. હવે, દરેક તત્વ માટે i એરેમાં:
    • If CNT શૂન્ય બરાબર છે:
      • અપડેટ કરો ઉમેદવાર = i
    • If i બરાબર છે ઉમેદવાર:
      • વૃદ્ધિ CNT: સીએનટી ++
    • બાકી:
      • ઘટાડો CNT: સી.એન.ટી.
  3. રીટર્ન ઉમેદવાર
  4. પરિણામ છાપો

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

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

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

int majorityElement(vector <int> &a)
{
    int candidate = -1 , cnt = 0;
    for(int &i : a)
    {
        if(cnt == 0)
            candidate = i;
        cnt += (candidate == i) ? 1 : -1;
    }
    return candidate;
}

int main()
{
    vector <int> a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
    cout << majorityElement(a) << '\n';
    return 0;
}

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

import java.util.*;

class majority_element
{
    public static void main(String args[])
    {
        int[] a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
        System.out.println(majorityElement(a));
    }

    static int majorityElement(int[] a)
    {
        int candidate = -1 , cnt = 0;
        for(int i = 0 ; i < a.length ; i++)
        {
            if(cnt == 0)
                candidate = a[i];
            cnt += (candidate == a[i]) ? 1 : -1;
        }
        return candidate;
    }
}
2

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

સમય જટિલતા

ઓ (એન) આપણે એક વાર આખા એરેને પસાર કરીએ છીએ. અહીં, N એરેનું = કદ.

અવકાશ જટિલતા

ઓ (1) જેમકે આપણે સતત મેમરી જગ્યા વાપરીએ છીએ.