Көпшілік элементі Leitcode шешімі


Күрделілік дәрежесі оңай
Жиі кіреді Amazon алма Atlassian Bloomberg Facebook GoDaddy Google Microsoft Oracle Рубрик Snapchat Yahoo Zenefits
Бөліңіз және жеңіңіз Хэш

Проблемалық мәлімдеме

Бізге ан массив бүтін сандар. Floor ⌋ еден операторы болатын массивте ⌊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 рет кездеседі.

Тәсіл (Hashtable)

Массивтегі әрбір элементтің жиілігін хэш-кестеде сақтай аламыз. Содан кейін жиілігі> ⌊N / 2 frequency болатын бүтін санды тексеру оңай болады.

Алгоритм

  1. Массивтегі бүтін сандардың жиілігін сақтау үшін хэш кестесін бастаңыз: жиілік
  2. Әр элемент үшін, i, массивте:
    • Көбею жиілігі [i] немесе орнатылған жиілігі [i] = 0 егер ол кестеде жоқ болса
    •  If жиілігі [i] > № 2:
      • қайту i
  3. Қайтару -1 (компиляция қателігін болдырмау үшін)
  4. Нәтижені басып шығарыңыз

Leitcode шешімінің көпшілігінің шешімі

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

Java бағдарламасы

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

Leitcode шешімінің көпшілігін талдау

Уақыттың күрделілігі

O (N) біз массивті бір рет айналып өтіп, көпшілік элементті табамыз. N = массивтің өлшемі.

Ғарыштың күрделілігі

O (N) массивтегі нақты элементтердің максималды саны келесідей болуы мүмкін: N - ⌊N / 2⌋ өйткені көпшілік элемент кем дегенде алады ⌊N / 2⌋ индекстер. Сондықтан кеңістіктің күрделілігі сызықтық болып табылады.

Тәсіл (Бойер-Мур дауыс беру алгоритмі)

Бұл мәселе элементтер ағынында көпшілік элементті қалай табуға болатындығы туралы жақсы мысал. Бойер-Мурға дауыс беру алгоритмі ⌊N / 2⌋-ден көп орынды алатын элементті табу үшін қолданылады. Бұл алгоритм а кандидат және оның санау массивте. Біз массивтің бір өтуін орындаймыз кандидат = -1 және санау = 0. Егер массивтің кез келген элементі кандидат, біз ұлғайтамыз санау. Әйтпесе, біз оны азайтамыз. Егер санау нөлге айналса, біз мәнін өзгертеміз кандидат және оны орнатыңыз санау 0-ге оралу.

Оның жұмысын түсіну үшін төмендегі мысалды орындаңыз:

Көпшілік элементі Leitcode шешімі

Бұл алгоритм процесті сайлау ретінде қарастырады және алдымен кандидатты анықтайды. Кім көп дауыс алса, ол көпшілік үміткер. Жоғарыда келтірілген мысалда біз үміткерді бастапқыда 1 деп таңдаймыз, бірақ массивтің 4 индексіне жеткенде санау = 0 болатынын байқаймыз, демек біз үміткерлерден көп кандидатты көрдік. Сонымен, біз қазіргі элементті үміткер ретінде таңдап, процесті жалғастырамыз. Біз болғандықтан кепілдік массивте көпшілік элементі болу үшін, бізде қалған соңғы үміткер көпшілік элемент болады.

Алгоритм

  1. Екі айнымалыны инициализациялаңыз: кандидат және ҰБТ кандидатты және оның қайталану жиілігін тиісті қайталанулар үшін сақтау
  2. Енді, әр элемент үшін i массивте:
    • If ҰБТ нөлге тең:
      • жаңарту: кандидат = i
    • If i тең кандидат:
      • өсім ҰБТ: cnt ++
    • Басқа:
      • Азаю ҰБТ: cnt–
  3. қайтару кандидат
  4. Нәтижені басып шығарыңыз

Leitcode шешімінің көпшілігінің шешімі

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

Java бағдарламасы

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

Leitcode шешімінің көпшілігін талдау

Уақыттың күрделілігі

O (N) біз бүкіл массивті бір рет айналып өткенде. Мұнда, N = массивтің өлшемі.

Ғарыштың күрделілігі

O (1) өйткені біз жадтың тұрақты кеңістігін қолданамыз.