Մեծամասնություն Element II Leetcode լուծում


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Adobe Amazon խնձոր Bloomberg facebook Google Microsoft Առավելությունները
Դասավորություն

Այս խնդրում մեզ տրվում է ան դասավորություն ամբողջ թվերի: Նպատակն է գտնել բոլոր այն տարրերը, որոնք առաջանում են ավելին ⌊N / 3⌋ ժամանակը զանգվածում, որտեղ N = զանգվածի չափը և ⌊ ⌋ - ը հատակի գործարկիչն է: Մենք պետք է վերադարձնենք նման տարրերի զանգված:

Տարրերի շարքը. -10 ^ 9 դեպի 10 ^ 9

Օրինակ

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

բացատրությունNowN / 3⌋ = ⌊5 / 3⌋ = 1. Այժմ, 2 և 3 ամբողջ թվերն ունեն 2-ի հավասար հաճախականություններ, ինչը ավելի մեծ է 1. Այսպիսով, մենք տպում ենք դրանք:

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

Բացատրությունը. Մենք այս դեպքում չգտանք որևէ տարր, որի հաճախականությունը 1-ից մեծ լինի: Այսպիսով, մենք տպում ենք «Ոչ մեծամասնության տարրեր»:

Մոտեցում (հաճախությունների պահպանում)

Ինչպես վերնագիրն է հուշում, մենք կարող ենք զանգվածում պահպանել յուրաքանչյուր տարրի հաճախականությունը `օգտագործելով հեշ աղյուսակ և այնուհետև ստուգել ավելի մեծ հաճախություն ունեցող տարրերի առկայությունը, ⌊N / 3⌋: Այսպիսով, մենք կարող ենք գտնել պայմանը բավարարող բոլոր տարրերը:

Ալգորիթմ

  1. Նախաձեռնեք HashMap-հաճախություն տարրերի հաճախականությունները զանգվածում և ցուցակում / վեկտորում պահելու համար արդյունք մեծամասնության տարրերը պահելու համար
  2. Յուրաքանչյուր տարրի համար զանգվածում.
    • Բարձրացնել դրա հաճախականությունը. հաճախականություն [i] ++ (կամ սահմանվել է 1, եթե արդեն առկա չէ)
  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

II մեծամասնության տարրերի լեոդ կոդերի լուծման բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ) քանի որ մենք մեկ անգամ անցնում ենք ամբողջ զանգվածը ՝ հաճախականությունները թարմացնելու համար: N = զանգվածի չափը:

Տիեզերական բարդություն

ՎՐԱ) քանի որ մենք օգտագործում ենք հաշ սեղան `հաճախությունները պահելու համար:

Մոտեցում (Բոյեր-Մուր քվեարկության ալգորիթմ)

Այստեղ առաջին բանը, որ պետք է նկատել, այն է, որ կարող են լինել առավելագույնը 2 տարր, քան հաճախականությամբ ավելի մեծ RayN / 3⌋ զանգվածում: Այսպիսով, այս խնդիրը դառնում է նույնը, ինչ Մեծամասնության տարր խնդիրը 2 մեծամասնության տարրերն այս անգամ:

Մենք արդեն լուծել ենք Մեծամասնության տարրերի խնդիրը ՝ օգտագործելով Բուեր-Մուրի քվեարկության ալգորիթմը: Միակ մեծամասնության տարրի դեպքում մենք կարող ենք օգտագործել ալգորիթմը ՝ համեմատելով ներկայիս էլեմենտը հավակնորդ է, թե ոչ: Բայց այս պարագայում մենք պետք է պահենք մեծամասնության երկու հավանական տարր և զուգահեռաբար թարմացնենք դրանց հաշվիչները: Այս ինտուիցիայի միջոցով մենք կարող ենք մեր պայմանները դնել հետևյալ կերպ.

  • Սահմանեք ցանկացած երկու պատահական թեկնածու զանգվածի տարրերի տիրույթից դուրս:
  • Եթե ​​տարրը հավասար է թեկնածուներից որևէ մեկին, ապա ավելացրեք դրա հաշվիչը:
  • Եթե ​​մեկ թեկնածուի հաշվիչը հավասար է 0 ցանկացած պահի, մենք ներկայիս տարրը դնում ենք որպես թեկնածու if այս ներկա տարրը մյուս թեկնածուն չէ:
  • Մենք նվազեցնում ենք երկու թեկնածուների հաշվիչները, եթե ներկայիս տարրը հավասար չէ թեկնածուներից ոչ մեկին:

Այս կերպ, մենք շարունակում ենք զանգվածում զուգահեռաբար պահպանել երկու տարբեր թեկնածուների, առանց առաջին թեկնածուի մյուսի վրա ազդելու: Այնուամենայնիվ, հնարավոր է, որ այն թեկնածուները, որոնց մոտ մենք հայտնվում ենք, իրական մեծամասնության տարրեր չեն ({1, 1, 2, 2, 3, 3} այդպիսի օրինակներից է): Ուստի անհրաժեշտ է կատարել երկրորդ փոխանցում ՝ թեկնածուների հաճախականությունները հաշվելու համար, որոնց արդյունքում մենք հայտնվում ենք: Դրա հիման վրա մենք կարող ենք վերադարձնել մեծամասնության տարրերի վեկտորը:

Ալգորիթմ

  1. initialize candOne և candtwo պահպանել երկու թեկնածուներին և դրանց հաճախականությունները cntOne և cntTwo as 0.
  2. Յուրաքանչյուր տարրի համար զանգվածում.
    • If candOne == ես:
      • cntOne++
    • ուրիշ եթե candTwo == i
      • cntTwo++
    • ուրիշ եթե cntOne == 0
      • Նշանակել i as candOne: candOne = ես
      • Դրա համարը սահմանեք 1: cntOne = 1
    • ուրիշ եթե cntTwo == 0
      • candTwo = ես
      • cntTwo = 1
    • Երկու թեկնածուների էլեկտրաէներգիայի հաշվարկը.
      • cntOne–
      • cnt երկու -
  3. Երկրորդ փոխանցման համար նրանց հաշվարկները վերադարձրեք զրոյի. cntOne = 0 և cntTwo = 0
  4. Rayանգվածի յուրաքանչյուր տարրի համար.
    • եթե այն հավասար է candOne- ին.
      • cntOne ++
    • ուրիշ, եթե դա հավասար է candTwo- ին:
      • cntTwo ++
  5. Նախաձեռնեք ցուցակը / վեկտորը արդյունք մեծամասնության տարրերը պահելու համար
  6. Եթե ​​cntOne> N / 3
    • Հրեք candOne դեպի արդյունք
  7. Եթե ​​cntTwo> N / 3
    • Հրեք candTwo դեպի արդյունք
  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

II մեծամասնության տարրերի լեոդ կոդերի լուծման բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ) երբ մենք վազում ենք զանգվածի երկու անցում ՝ անկախ մուտքից: N = զանգվածի չափը:

Տիեզերական բարդություն

Ո (1) քանի որ մենք անընդհատ հիշողություն ենք ունենում: