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


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፓም Atlassian ብሉምበርግ ፌስቡክ GoDaddy google የ Microsoft በ Oracle ክፍል Snapchat ያሁ ዘይቶች
አካፍል እና ድል ሃምሽንግ

የችግሩ መግለጫ

ተሰጠን ደርድር የቁጥር ቁጥሮች። ⌊ 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] ወይም ያዘጋጁ ድግግሞሽ [i] = 0 ቀድሞውኑ በሰንጠረ in ውስጥ ካልሆነ
    •  If ድግግሞሽ [i] > N / 2:
      • መመለስ እኔ
  3. መመለስ -1 (የማጠናቀር ስህተትን ለማስወገድ)
  4. ውጤቱን ያትሙ

የብዙዎች ንጥረ ነገር ሌትኮድ መፍትሔ አተገባበር

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 - ⌊N / 2⌋ ምክንያቱም አብዛኛው አካል ቢያንስ ይይዛል ⌊N / 2⌋ ማውጫዎች ስለዚህ የቦታ ውስብስብነት መስመራዊ ነው።

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

ይህ ችግር በንጥረ ነገሮች ጅረት ውስጥ ብዙውን አካል እንዴት ማግኘት እንደምንችል ጥሩ ማሳያ ነው ፡፡ የቦየር-ሙር ድምጽ አሰጣጥ ስልተ-ቀመር ከ ⌊N / 2⌋ በላይ ቦታዎችን በቅደም ተከተል የሚይዝ ንጥረ ነገር ለማግኘት ጥቅም ላይ ይውላል ፡፡ ይህ ስልተ ቀመር ሀ እጩ እና የእሱ ተጐዳሁ: በድርድሩ ውስጥ ከድርድሩ አንድ ነጠላ ማለፊያ እናካሂዳለን እጩ = -1 እና ተጐዳሁ: = 0. በድርድሩ ውስጥ ያለ ማንኛውም ንጥረ ነገር ከሆነ እጩ፣ እንጨምራለን ቆጠረ። አለበለዚያ እኛ እንቀንሳለን ፡፡ ቆጠራው ዜሮ ከሆነ እኛ እንለውጣለን እጩ እና ያቀናብሩ ተጐዳሁ: ወደ 0 ተመለስ ፡፡

ሥራውን ለመረዳት ከዚህ በታች ያለውን ምሳሌ ይከተሉ

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

ይህ ስልተ ቀመር ሂደቱን እንደ ምርጫ በመቁጠር በመጀመሪያ እጩን ይወስናል ፡፡ ብዙ ድምፅ ያገኘው የአብዛኛው ተወዳዳሪ ነው ፡፡ ከላይ በተጠቀሰው ምሳሌ ውስጥ እጩን በመጀመሪያ እንደ 1 እንመርጣለን ፣ ግን በድርድሩ ውስጥ ጠቋሚ 4 ላይ ስንደርስ ያንን ቁጥር = 0 እናስተውላለን ፣ ይህም ማለት እንደ እጩ ተወዳዳሪ ያልሆኑ ያህል ብዙ እጩዎችን አይተናል ማለት ነው ፡፡ ስለዚህ የአሁኑን አባል እንደ እጩ እንመርጣለን እና ሂደቱን እንቀጥላለን። እኛ ስለሆንን የተረጋገጠ በምድቡ ውስጥ ብዙ አባል እንዲኖር ፣ የቀረነው የመጨረሻው እጩ የብዙሃኑ አባል ይሆናል።

አልጎሪዝም

  1. ሁለት ተለዋዋጮችን ያስጀምሩ እጩ cnt እጩውን እና ድግግሞሹን ለተለያዩ ድግግሞሾች ለማከማቸት
  2. አሁን ለእያንዳንዱ ንጥረ ነገር i በድርድሩ ውስጥ
    • If cnt ከዜሮ ጋር እኩል ነው
      • ዝመና እጩ = እኔ
    • If i እኩል ነው እጩ:
      • ጭማሪ cnt: cnt ++
    • ሌላ
      • ቅነሳ cnt: cnt–
  3. ተመለስ እጩ
  4. ውጤቱን ያትሙ

የብዙዎች ንጥረ ነገር ሌትኮድ መፍትሔ አተገባበር

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) የማያቋርጥ የማስታወሻ ቦታ እንደምንጠቀም ፡፡