మెజారిటీ ఎలిమెంట్ లీట్‌కోడ్ సొల్యూషన్


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ ఆపిల్ Atlassian బ్లూమ్బెర్గ్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> GoDaddy గూగుల్ మైక్రోసాఫ్ట్ ఒరాకిల్ విభాగం Snapchat యాహూ జెనెఫిట్స్
విభజించు పాలించు హ్యాషింగ్

సమస్యల నివేదిక

మాకు ఒక ఇవ్వబడింది అమరిక పూర్ణాంకాల. మేము the the ఫ్లోర్ ఆపరేటర్ అయిన శ్రేణిలో ⌊N / 2⌋ సమయం కంటే ఎక్కువ సంభవించే పూర్ణాంకాన్ని తిరిగి ఇవ్వాలి. ఈ మూలకాన్ని మెజారిటీ మూలకం అంటారు. ఇన్పుట్ శ్రేణి ఎల్లప్పుడూ మెజారిటీ మూలకాన్ని కలిగి ఉంటుందని గమనించండి.

ఉదాహరణ

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] లేదా సెట్ చేయండి పౌన frequency పున్యం [i] = 0 ఇది ఇప్పటికే పట్టికలో లేకపోతే
    •  If ఫ్రీక్వెన్సీ [i] > ఎన్ / 2:
      • తిరిగి నేను
  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 - ⌊N / 2⌋ మెజారిటీ మూలకం కనీసం ఆక్రమించినందున ⌊N / 2⌋ సూచీలు. కాబట్టి, స్థల సంక్లిష్టత సరళంగా ఉంటుంది.

అప్రోచ్ (బోయెర్-మూర్ ఓటింగ్ అల్గోరిథం)

ఈ సమస్య మూలకాల ప్రవాహంలో మెజారిటీ మూలకాన్ని ఎలా కనుగొనగలదో చక్కని ఉదాహరణ. ఒక క్రమంలో ⌊N / 2⌋ కంటే ఎక్కువ స్థలాలను ఆక్రమించే మూలకాన్ని కనుగొనడానికి బోయెర్-మూర్ ఓటింగ్ అల్గోరిథం ఉపయోగించబడుతుంది. ఈ అల్గోరిథం a అభ్యర్థి మరియు దాని కౌంట్ శ్రేణిలో. మేము శ్రేణి యొక్క ఒకే పాస్‌ను నడుపుతాము అభ్యర్థి = -1 మరియు కౌంట్ = 0. శ్రేణిలోని ఏదైనా మూలకం ఉంటే అభ్యర్థి, మేము పెంచుతాము కౌంట్. లేకపోతే, మేము దానిని తగ్గిస్తాము. గణన సున్నాగా మారితే, మేము దానిని మారుస్తాము అభ్యర్థి మరియు దాని సెట్ కౌంట్ తిరిగి 0 కి.

దాని పనితీరును అర్థం చేసుకోవడానికి, క్రింది ఉదాహరణను అనుసరించండి:

మెజారిటీ ఎలిమెంట్ లీట్‌కోడ్ సొల్యూషన్

ఈ అల్గోరిథం ఈ ప్రక్రియను ఎన్నికగా పరిగణిస్తుంది మరియు మొదట అభ్యర్థిని నిర్ణయిస్తుంది. ఎక్కువ ఓట్లు పొందిన వ్యక్తి మెజారిటీ అభ్యర్థి. పై ఉదాహరణలో, మేము ఒక అభ్యర్థిని మొదట్లో 1 గా ఎన్నుకుంటాము, కాని మేము శ్రేణిలో ఇండెక్స్ 4 కి చేరుకున్నప్పుడు, ఆ గణన = 0 ను గమనించాము, అంటే అభ్యర్థులను కాని అభ్యర్థులుగా ఎక్కువ మంది అభ్యర్థులను చూశాము. కాబట్టి, మేము ప్రస్తుత మూలకాన్ని అభ్యర్థిగా ఎన్నుకుంటాము మరియు ప్రక్రియను కొనసాగిస్తాము. మేము కాబట్టి హామీ శ్రేణిలో మెజారిటీ మూలకాన్ని కలిగి ఉండటానికి, మనకు మిగిలి ఉన్న చివరి అభ్యర్థి మెజారిటీ మూలకం.

అల్గారిథం

  1. రెండు వేరియబుల్స్ ప్రారంభించండి: అభ్యర్థి మరియు cnt సంబంధిత పునరావృతాల కోసం అభ్యర్థిని మరియు దాని పౌన frequency పున్యాన్ని నిల్వ చేయడానికి
  2. ఇప్పుడు, ప్రతి మూలకం కోసం i శ్రేణిలో:
    • If cnt సున్నాకి సమానం:
      • నవీకరణ: అభ్యర్థి = i
    • If i సమానం అభ్యర్థి:
      • ఇంక్రిమెంట్ cnt: cnt ++
    • లేకపోతే:
      • తగ్గుదల 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 = శ్రేణి యొక్క పరిమాణం.

అంతరిక్ష సంక్లిష్టత

O (1) మేము స్థిరమైన మెమరీ స్థలాన్ని ఉపయోగిస్తున్నప్పుడు.