အများစု Element ကို II ကို Leetcode ဖြေရှင်းချက်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Adobe က အမေဇုံ Apple ဘလွန်းဘာ့ဂ် Facebook က Google Microsoft က အကျိုးအမြတ်
အခင်းအကျင်း

ဒီပြproblemနာမှာငါတို့ကိုပေးထားတယ် အခင်းအကျင်း ကိန်း၏။ အဆိုပါရည်မှန်းချက်ထက်ပိုပေါ်ပေါက်သောဒြပ်စင်အပေါငျးတို့သကိုရှာဖွေရန်ဖြစ်ပါသည် /N / 3⌋ N ကို = ခင်းကျင်း၏အရွယ်အစားနှင့် floor floor ကြမ်းပြင်အော်ပရေတာသည်အဘယ်မှာရှိခင်းကျင်းအတွက်အချိန်။ ကျွန်ုပ်တို့သည်ထိုကဲ့သို့သောဒြပ်စင်များစွာကိုပြန်ပို့ရန်လိုအပ်သည်။

ဒြပ်စင်များ၏အကျယ်: -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 ထက်ပိုမိုသောမည်သည့်ဒြပ်စင်ကိုမျှကျွန်ုပ်တို့ရှာမတွေ့ပါ။ ဒါကြောင့်“ No Majority element” ကိုပုံနှိပ်တယ်။

ချဉ်းကပ်နည်း (ကြိမ်နှုန်းများကိုသိုလှောင်ခြင်း)

ခေါင်းစဉ်ဖော်ပြသည့်အတိုင်းကျွန်ုပ်တို့သည် hash table ကိုအသုံးပြုပြီး array အတွင်းရှိ element တိုင်း၏ကြိမ်နှုန်းကိုသိုလှောင်နိုင်ပြီးကြိမ်နှုန်းထက်ပိုသော element များကိုစစ်ဆေးနိုင်သည်။ /N / 3⌋။ ဤနည်းအားဖြင့်ကျွန်ုပ်တို့သည်အခြေအနေကိုဖြည့်ဆည်းပေးနိုင်သည့်ဒြပ်စင်အားလုံးကိုရှာတွေ့နိုင်သည်။

algorithm

  1. HashMap ကိုစတင်ပါ။အကြိမ်ရေ ဒြပ်စင်များ၏ကြိမ်နှုန်းကိုခင်းကျင်းပြသခြင်းနှင့်စာရင်း / အားသွင်းခြင်းတို့ဖြင့်သိမ်းဆည်းရန် ရလဒ် အများစုဒြပ်စင်သိုလှောင်ရန်
  2. ဒြပ်စင်တိုင်းသည် ခင်းကျင်းထဲမှာ:
    • ၎င်း၏ကြိမ်နှုန်းကိုတိုး: ကြိမ်နှုန်း [i] ++ (သို့မဟုတ်မရှိလျှင် ၁ အဖြစ်သတ်မှတ်ထားပါက)
  3. တိုင်းအတွက် သော့ hashmap မှာ:
    1. If ကြိမ်နှုန်း [သော့] > N / 3
      1. အဲဒါကိုထည့်ပါ ရလဒ်
  4. စာရင်းကိုပြန်သွားပါ ရလဒ်

အများစု Element II ကို Leetcode ဖြေရှင်းချက်၏အကောင်အထည်ဖော်မှု

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;
}

Java အစီအစဉ်

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

အများစု Element ကို II ကို Leetcode ဖြေရှင်းချက်၏ရှုပ်ထွေးခွဲခြမ်းစိတ်ဖြာ

အချိန်ရှုပ်ထွေး

အို (N) ကျနော်တို့ကြိမ်နှုန်းကို update လုပ်ဖို့တစ်ချိန်ကခင်းကျင်းတစ်ခုလုံးကိုဖြတ်သန်းသွားသည်နှင့်အမျှ။ N = ခင်းကျင်း၏အရွယ်အစား။

အာကာသရှုပ်ထွေးမှု

အို (N) ကျွန်ုပ်တို့သည်ကြိမ်နှုန်းကိုသိမ်းဆည်းရန် hash table ကိုအသုံးပြုသည်။

ချဉ်းကပ်မှု (Boyer-Moore မဲပေးခြင်း Algorithm)

ဒီမှာသတိပြုရမယ့်အချက်ကတော့ကြိမ်နှုန်းထက်ပိုသောဒြပ်စင် ၂ ခုရှိနိုင်သည် ခင်းကျင်းအတွက် N / 3⌋။ ဒီတော့ဒီပြproblemနာကအတူတူပဲဖြစ်လာတယ် အများစု Element ကို ပြနာ 2 အများစုဒြပ်စင်ဒီအချိန်။

Boyer-Moore ၏ Voting Algorithm ကို အသုံးပြု၍ Majority Element ပြproblemနာကိုကျွန်ုပ်တို့ဖြေရှင်းပြီးပါပြီ။ တစ်ခုတည်းသောအများစုဒြပ်စင်တစ်ခုအနေဖြင့်ကျွန်ုပ်တို့သည်လက်ရှိဒြပ်စင်သည်ကိုယ်စားလှယ်လောင်းဟုတ်မဟုတ်နှိုင်းယှဉ်ခြင်းအားဖြင့် algorithm ကိုအသုံးပြုနိုင်သည်။ သို့သော်ဤကိစ္စတွင်ကျွန်ုပ်တို့သည်ဖြစ်နိုင်ချေရှိသောအများစုသောဒြပ်စင်နှစ်ခုကိုကိုင်ထားပြီးသူတို့၏ကောင်တာများကိုတစ်ပြိုင်တည်းမွမ်းမံရန်လိုအပ်သည်။ ဤပင်ကိုယ်စွမ်းရည်၏အကူအညီဖြင့်ကျွန်ုပ်တို့၏အခြေအနေများကိုအောက်ပါအတိုင်းသတ်မှတ်နိုင်သည်။

  • မည်သည့်ကျပန်းကိုယ်စားလှယ်လောင်းနှစ် ဦး ကိုမဆိုခင်းကျင်းထဲရှိဒြပ်စင်များ၏အကွာအဝေးပြင်ပတွင်ထားပါ။
  • အကယ်၍ element သည်ကိုယ်စားလှယ်လောင်းတစ် ဦး ဦး နှင့်တူညီနေလျှင်၎င်း၏ counter ကိုမြှောက်ပါ။
  • ကိုယ်စားလှယ်လောင်းတစ် ဦး ၏ကောင်တာညီမျှလျှင် 0 မည်သည့်အချက်မဆိုကျနော်တို့လက်ရှိ element ကိုကိုယ်စားလှယ်လောင်းအဖြစ်ထားကြ၏ if ဒီလက်ရှိဒြပ်စင်အခြားကိုယ်စားလှယ်လောင်းမဟုတ်ပါဘူး။
  • လက်ရှိ element သည်ကိုယ်စားလှယ်လောင်းနှစ် ဦး နှင့်တူညီခြင်းမရှိပါကကျွန်ုပ်တို့သည်နှစ် ဦး စလုံးအတွက်နှစ် ဦး စလုံး၏ကောင်တာကိုလျော့နည်းစေသည်။

ဤနည်းအားဖြင့်ကျွန်ုပ်တို့သည်ပထမ ဦး ဆုံးကိုယ်စားလှယ်လောင်းသည်အခြားတစ် ဦး ကိုထိခိုက်ခြင်းမရှိဘဲကွဲပြားခြားနားသောကိုယ်စားလှယ်လောင်းနှစ် ဦး ကိုထပ်တူကျစွာဆက်လက်ထိန်းသိမ်းထားသည်။ သို့သျောလညျး, ငါတို့နှင့်အတူအဆုံးသတ်ကိုယ်စားလှယ်လောင်းများစစ်မှန်သောအများစုဒြပ်စင်မဟုတ်ကြောင်းဖြစ်နိုင်သည် ({1, 1, 2, 2, 3, 3} ထိုကဲ့သို့သောဥပမာတစ်ခုဖြစ်သည်) ။ ထို့ကြောင့်ကျွန်ုပ်တို့နောက်ဆုံးအဆုံးသတ်ထားသောကိုယ်စားလှယ်လောင်းများ၏ကြိမ်နှုန်းကိုရေတွက်ရန်ဒုတိယအကြိမ်သွားရန်လိုအပ်သည်။ ၎င်းကို အခြေခံ၍ ကျွန်ုပ်တို့သည်အများစုသောဒြပ်စင်များ၏အားနည်းချက်ကိုပြန်ပို့နိုင်သည်။

algorithm

  1. စတငျ ပုန်း နှင့် ကွမ်းခြံကုန်း နှစ်ခုကိုယ်စားလှယ်လောင်းများနှင့်၎င်းတို့၏ကြိမ်နှုန်းသိုလှောင်ရန် နေပြည်တော် နှင့် နေပြည်တော် as 0.
  2. ဒြပ်စင်တိုင်းသည် ခင်းကျင်းထဲမှာ:
    • If candOne == ငါ:
      • နေပြည်တော်++
    • ကျန်တဲ့ နှစ် ဦး == i
      • နေပြည်တော်++
    • အခြား cn လျှင်One == 0
      • သတ်မှတ် i as ပုန်း: candOne = ဈ
      • အရေအတွက်ကို ၁ အဖြစ်သတ်မှတ်ပါ။ cntOne = 1
    • ကျန်တဲ့ cntTwo == 0 င
      • candTwo = ဈ
      • cntTwo = 1
    • ကိုယ်စားလှယ်လောင်းနှစ် ဦး စလုံး၏လျှော့ချအရေအတွက်
      • cntOne-
      • cntTwo–
  3. ဒုတိယအကြိမ်အရေအတွက်ကိုရေတွက်ပါ။ cntOne = 0 နှင့် cntTwo = 0
  4. Array ထဲက element တိုင်းအတွက်:
    • candOne နဲ့ညီရင်
      • cntOne ++
    • candTwo နဲ့ညီမယ်ဆိုရင်။
      • cntTwo ++
  5. စာရင်း / အားနည်းချက်ကိုအစပြုပါ ရလဒ် အများစုဒြပ်စင်သိုလှောင်ရန်
  6. cntOne> N / 3 လျှင်
    • တွန်းထိုး ပုန်း သို့ ရလဒ်
  7. cntTwo> N / 3 လျှင်
    • တွန်းထိုး နှစ် ဦး သို့ ရလဒ်
  8. ရလဒ်ပုံနှိပ်ပါ

ပုံဥပမာ:

အများစု Element ကို II ကို Leetcode ဖြေရှင်းချက်

အများစု Element II ကို Leetcode ဖြေရှင်းချက်၏အကောင်အထည်ဖော်မှု

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;
}

Java အစီအစဉ်

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

အများစု Element ကို II ကို Leetcode ဖြေရှင်းချက်၏ရှုပ်ထွေးခွဲခြမ်းစိတ်ဖြာ

အချိန်ရှုပ်ထွေး

အို (N) ကျနော်တို့မသက်ဆိုင်ဘဲမူလ input ကို၏ခင်းကျင်းနှစ်ခု 'passes run အဖြစ်။ N = ခင်းကျင်း၏အရွယ်အစား။

အာကာသရှုပ်ထွေးမှု

အို (၁) ကျွန်တော်စဉ်ဆက်မပြတ်မှတ်ဉာဏ်အာကာသအဖြစ်။