अधिकांश तत्व एलिटकोड समाधान


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना सेब Atlassian ब्लूमबर्ग Facebook पिताजी जाओ गूगल माइक्रोसॉफ्ट ओरेकल अनुभाग Snapchat याहू ज़ेनफ़िट्स
विभाजन और जीत hashing

समस्या का विवरण

हमें ए सरणी पूर्णांकों की। हमें पूर्णांक को वापस करने की आवश्यकता है जो उस सरणी में toN / 2⌋ समय से अधिक होता है जहां inte operator तल ऑपरेटर है। इस तत्व को बहुमत तत्व कहा जाता है। ध्यान दें कि इनपुट सरणी में हमेशा बहुमत तत्व होता है।

उदाहरण

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

छूटना: 2.N / 4⌋ = 2/2 = 3. और पूर्णांक '3' सरणी में XNUMX बार होता है।

Array = {1 , 1 , 2}
1

व्याख्या: ⌋N / 2⌋ = ⌊3 / 2 1. = 1. और '2' सरणी में XNUMX बार होता है।

दृष्टिकोण (हैशटेबल)

हम सरणी में हर तत्व की आवृत्ति को हैश तालिका में संग्रहीत कर सकते हैं। तब एक पूर्णांक आवृत्ति> ⌋N / 2 check के लिए जांचना आसान हो जाता है।

कलन विधि

  1. सरणी में पूर्णांकों की आवृत्ति को संग्रहीत करने के लिए एक हैश तालिका प्रारंभ करें: आवृत्ति
  2. हर तत्व के लिए, iसरणी में:
    • वेतन वृद्धि आवृत्ति [i] या सेट आवृत्ति [i] = ० यदि यह पहले से ही तालिका में नहीं है
    •  If आवृत्ति [i] > एन / 2:
      • मैं लौटा
  3. रिटर्न -1 (संकलन त्रुटि से बचने के लिए)
  4. परिणाम प्रिंट करें

बहुसंख्यक तत्व Leetcode Solution का कार्यान्वयन

C ++ प्रोग्राम

#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 शून्य के बराबर है:
      • अद्यतन करें: उम्मीदवार = मैं
    • If i के बराबर है उम्मीदवार:
      • वेतन वृद्धि cnt: cnt ++
    • अन्य:
      • घटती cnt: सीएनटी-
  3. वापसी उम्मीदवार
  4. परिणाम प्रिंट करें

बहुसंख्यक तत्व Leetcode Solution का कार्यान्वयन

C ++ प्रोग्राम

#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) जैसा कि हम निरंतर मेमोरी स्पेस का उपयोग करते हैं।