የአብላጫ አካል II ሌትኮድ መፍትሔ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን ፓም ብሉምበርግ ፌስቡክ google የ Microsoft ዘይቶች
ሰልፍ

በዚህ ችግር ውስጥ እኛ አንድ ተሰጠን ደርድር የቁጥር ቁጥሮች። ግቡ የበለጠ የሚከሰቱትን ሁሉንም አካላት መፈለግ ነው ⌊N / 3⌋ N = የአቀማመጥ መጠን እና ⌊ the ወለል ኦፕሬተር በሆነበት ድርድር ውስጥ ያለው ጊዜ። እንደነዚህ ያሉ ንጥረ ነገሮችን አንድ ስብስብ መመለስ አለብን።

የንጥረ ነገሮች ክልል -10 ^ 9 ወደ 10 ^ 9

ለምሳሌ

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

ማስረጃ⌊N / 3⌋ = ⌊5 / 3⌋ = 1. አሁን ቁጥሮቹ 2 እና 3 ከ 2 ጋር እኩል ድግግሞሾች አሏቸው ፣ ይህም የበለጠ ነው 1. ስለዚህ እኛ እናተምባቸዋለን ፡፡

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

ማብራሪያ: በዚህ ጉዳይ ላይ ድግግሞሹ ከ 1 የሚበልጥ አካል አላገኘንም ፡፡ ስለዚህ ፣ “ብዙ ቁጥር ያላቸው አባሎች የሉም” እናተማለን።

አቀራረብ (ድግግሞሾችን ማከማቸት)

ርዕሱ እንደሚጠቁመው ፣ የሃሽ ሰንጠረዥን በመጠቀም የእያንዳንዱን ንጥረ ነገር ድግግሞሽ በድርድሩ ውስጥ ማከማቸት እና ከዚያ የበለጠ ድግግሞሽ ያላቸው አባሎችን መመርመር እንችላለን ⌊N / 3⌋ በዚህ መንገድ ሁኔታውን የሚያሟሉ ሁሉንም አካላት ማግኘት እንችላለን ፡፡

አልጎሪዝም

  1. የሃሽ ማፕን ያስጀምሩመደጋገም በድርጅቱ ውስጥ ያሉትን ንጥረ ነገሮች ድግግሞሽ እና ዝርዝር / ቬክተር ለማከማቸት ውጤት ብዙዎቹን አካላት ለማከማቸት
  2. ለእያንዳንዱ ንጥረ ነገር በድርድሩ ውስጥ
    • ድግግሞሹን ይጨምሩ ድግግሞሽ [i] ++ (ወይም አሁን ከሌለው እንደ 1 ተቀናብሮ)
  3. ለያንዳንዱ ቁልፍ በሃሽፕ ውስጥ
    1. If ድግግሞሽ [ቁልፍ] > N / 3
      1. ወደ ላይ አክል ውጤት
  4. ዝርዝሩን ይመልሱ ውጤት

የብዙዎች ንጥረ ነገር አተገባበር II Leetcode Solution

C ++ ፕሮግራም

#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 Leetcode Solution

የጊዜ ውስብስብነት

ኦ (ኤን) ድግግሞሾችን ለማዘመን አንድ ጊዜ መላውን ድርድር ስናልፍ ፡፡ N = የድርድሩ መጠን።

የቦታ ውስብስብነት

ኦ (ኤን) ድግግሞሾችን ለማከማቸት የሃሽ ሰንጠረዥን እንጠቀማለን ፡፡

አቀራረብ (የቦየር-ሙር ድምጽ አሰጣጥ ስልተ-ቀመር)

እዚህ ላይ ልብ ሊባል የሚገባው የመጀመሪያው ነገር ቢበዛ ከ 2 በላይ ድግግሞሽ ያለው ከፍተኛ ንጥረ ነገሮች ሊኖሩ ይችላሉ በድርድሩ ውስጥ ⌊N / 3⌋ ስለዚህ ይህ ችግር እንደ አንድ አይነት ይሆናል የአብላጫ አካል ችግር ያለበት በ 2 በዚህ ጊዜ ብዙ አካላት።

የቦየር-ሙር የምርጫ ስልተ-ቀመርን በመጠቀም የአብዛኛውን ንጥረ ነገር ችግር ቀድሞውኑ ፈትተናል ፡፡ በአንዱ የብዙ አባል አካል ፣ የአሁኑ ንጥረ-ነገር እጩው አለመሆኑን በማወዳደር ስልተ ቀመሩን ልንጠቀምበት እንችላለን ፡፡ ግን ፣ በዚህ ሁኔታ ፣ ሁለት ሊሆኑ የሚችሉ ብዙ አባላትን መያዝ እና ቆጣሪዎቻቸውን በተመሳሳይ ማዘመን ያስፈልገናል ፡፡ በዚህ ውስጠ-ህሊና እገዛ ሁኔታችንን እንደሚከተለው መወሰን እንችላለን-

  • በድርድሩ ውስጥ ከሚገኙት ንጥረ ነገሮች ክልል ውጭ ማንኛውንም ሁለት የዘፈቀደ እጩዎችን ያዘጋጁ።
  • ንጥረ ነገሩ ከሁለቱም እጩዎች ጋር እኩል ከሆነ ቆጣሪውን ይጨምሩ።
  • የአንድ እጩ ቆጣሪ እኩል ከሆነ 0 በማንኛውም ጊዜ የአሁኑን ንጥረ-ነገር እንደ እጩ አድርገናል if ይህ የአሁኑ አባል ሌላኛው እጩ አይደለም ፡፡
  • የአሁኑ ንጥረ ነገር ከሁለቱም እጩዎች ጋር እኩል ካልሆነ የሁለቱን እጩዎች ቆጣሪዎች እንቀንሳለን ፡፡

በዚህ መንገድ የመጀመሪያው እጩ በሌላው ላይ ተጽዕኖ ሳያሳድር ሁለት የተለያዩ እጩዎችን በቅደም ተከተል በድርድር መያዛችንን እንቀጥላለን ፡፡ ሆኖም ፣ ይህ ሊሆን የቻልናቸው እጩዎች እውነተኛ የአብዛኞቹ አካላት አይደሉም ({1, 1, 2, 2, 3, 3} እንደዚህ ያሉ ምሳሌዎች ናቸው) ፡፡ ስለሆነም የምንደርስባቸውን የእጩዎች ድግግሞሽ ለመቁጠር ሁለተኛ መተላለፊያን ማስኬድ አስፈላጊ ነው ፡፡ ከዚህ በመነሳት የአብዛኞቹን አካላት ቬክተር መመለስ እንችላለን ፡፡

አልጎሪዝም

  1. ያስጀምሩ አንድሁለት ሁለቱን እጩዎች እና ድግግሞሾቻቸውን ለማከማቸት አንድሁለት as 0.
  2. ለእያንዳንዱ ንጥረ ነገር በድርድሩ ውስጥ
    • If candOne == i:
      • አንድ++
    • ሌላ ከሆነ ሁለት == i
      • ሁለት++
    • ሌላ ከሆነ cnአንድ == 0
      • መድብ i as አንድ: candOne = i
      • ቁጥሩን እንደ 1 ያዘጋጁ cntOne = 1
    • ሌላ ከሆነ cntTwo == 0
      • ሁለት = i
      • ሁለት = 1
    • የሁለቱም እጩዎች ቆጠራ-
      • cntOne–
      • ሁለት
  3. ለሁለተኛው ማለፊያ ቁጥሮቻቸውን ወደ ዜሮ ያቀናብሩ- cntOne = 0ሁለት = 0
  4. በድርድሩ ውስጥ ላሉት እያንዳንዱ ንጥረ ነገሮች
    • ከአንድ ጋር እኩል ከሆነ
      • cntOne ++
    • ሌላ ከካድስ ጋር እኩል ከሆነ
      • cntTwo ++
  5. ዝርዝር / ቬክተርን ያስጀምሩ ውጤት ብዙ አባላትን ለማከማቸት
  6. CntOne> N / 3 ከሆነ
    • ይግፉ አንድ ወደ ውጤት
  7. CntTwo> N / 3 ከሆነ
    • ይግፉ ሁለት ወደ ውጤት
  8. ውጤቱን ያትሙ

ስዕል:

የአብላጫ አካል II ሌትኮድ መፍትሔ

የብዙዎች ንጥረ ነገር አተገባበር II Leetcode Solution

C ++ ፕሮግራም

#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 Leetcode Solution

የጊዜ ውስብስብነት

ኦ (ኤን) ግብዓቱ ምንም ይሁን ምን ሁለት ድርድርን ስንሮጥ ፡፡ N = የድርድሩ መጠን።

የቦታ ውስብስብነት

ኦ (1) እኛ ቋሚ የማስታወሻ ቦታ እንደመሆናችን።