बहुमत घटक लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन सफरचंद Atlassian ब्लूमबर्ग फेसबुक GoDaddy Google मायक्रोसॉफ्ट ओरॅकल विभाग Snapchat याहू झेनफिट्स
विभाजित आणि विजय हॅशिंग

समस्या विधान

आम्हाला एक दिले जाते अॅरे पूर्णांक आम्हाला अ‍ॅरेमध्ये ⌊N / 2⌋ वेळेपेक्षा जास्त पूर्णांक पूर्ण करणे आवश्यक आहे जेथे occurs ⌊ मजला ऑपरेटर आहे. या घटकास बहुसंख्य घटक म्हणतात. लक्षात ठेवा इनपुट अ‍ॅरेमध्ये नेहमीच बहुसंख्य घटक असतात.

उदाहरण

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:
      • परत आय
  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 अ‍ॅरेचा आकार.

स्पेस कॉम्प्लेक्सिटी

ओ (एन) अ‍ॅरेमध्ये भिन्न घटकांची जास्तीत जास्त संख्या असू शकते. एन - ⌊एन / 2⌋ कारण बहुसंख्य घटक कमीतकमी व्यापतात /N / 2⌋ निर्देशांक. म्हणून, अंतराळ गुंतागुंत रेषात्मक आहे.

दृष्टीकोन (बॉयूर-मूर व्होटिंग अल्गोरिदम)

घटकांच्या प्रवाहात बहुसंख्य घटक कसे मिळू शकतात याचे एक छान उदाहरण ही समस्या आहे. बॉयर-मूर व्होटिंग अल्गोरिदम एका अनुक्रमात ⌊N / 2⌋ पेक्षा जास्त ठिकाणी व्यापणारा घटक शोधण्यासाठी वापरला जातो. हे अल्गोरिदम राखते a उमेदवार आणि त्याचे गणना अ‍ॅरे मध्ये. आम्ही अ‍ॅरेचा एकच पास सोबत चालवितो उमेदवार = -1 आणि गणना अ‍ॅरे मधील कोणतेही घटक असल्यास उमेदवार, आम्ही वाढ मोजा. अन्यथा, आम्ही ते कमी करतो. जर गणना शून्य झाली तर आपण बदलू उमेदवार आणि सेट करा गणना 0 वर परत.

त्याचे कार्य समजण्यासाठी, खालील उदाहरणाचे अनुसरण करा:

बहुमत घटक लीटकोड सोल्यूशन

हे अल्गोरिदम प्रक्रियेस निवडणूक मानतो आणि प्रथम उमेदवाराचा निर्णय घेते. ज्याला सर्वाधिक मते मिळतात तो बहुमताचा उमेदवार असतो. वरील उदाहरणात, आम्ही प्रारंभी 1 उमेदवार निवडतो, परंतु आपण अ‍ॅरे मध्ये निर्देशांक 4 वर पोहोचताच आपण ती संख्या = 0 पाहिली, म्हणजे आपण उमेदवार नसलेले जितके उमेदवार पाहिले आहेत. म्हणून आम्ही उमेदवार म्हणून विद्यमान घटक निवडतो आणि प्रक्रिया सुरू ठेवतो. आम्ही असल्याने हमी अ‍ॅरेमध्ये बहुमत घटक असण्यासाठी, आम्ही सोडलेला शेवटचा उमेदवार बहुमत घटक असेल.

अल्गोरिदम

  1. दोन चल प्रारंभ करा: उमेदवार आणि CNT उमेदवार संचयित करण्यासाठी आणि संबंधित पुनरावृत्तीसाठी त्याची वारंवारता
  2. आता, प्रत्येक घटकासाठी i अ‍ॅरेमध्ये:
    • If CNT शून्याच्या बरोबर आहे:
      • अद्यतनः उमेदवार = i
    • If i च्या बरोबर आहे उमेदवार:
      • वाढ 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 अ‍ॅरेचा आकार.

स्पेस कॉम्प्लेक्सिटी

ओ (1) आपण सतत मेमरी स्पेस वापरत आहोत.