Решење Леетцоде већине Елемент ИИ


Ниво тешкоће Средњи
Често питани у адобе амазонка јабука Блоомберг фацебоок гоогле мицрософт Зенефитс
Ред

У овом проблему добијамо поредак целих бројева. Циљ је пронаћи све елементе који се јављају више од ⌊Н / 3⌋ време у низу где је Н = величина низа, а ⌊ ⌋ подни оператор. Морамо да вратимо низ таквих елемената.

Распон елемената: -10 ^ 9 до 10 ^ 9

Пример

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

Објашњење⌊Н / 3⌋ = ⌊5 / 3⌋ = 1. Сада, цели бројеви 2 и 3 имају фреквенције једнаке 2, што је веће 1. Дакле, ми их исписујемо.

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

objašnjenje: У овом случају нисмо пронашли ниједан елемент чија је фреквенција већа од 1. Дакле, штампамо „Нема већинских елемената“.

Приступ (чување фреквенција)

Као што наслов сугерише, можемо похранити фреквенцију сваког елемента у низу помоћу хеш табеле, а затим проверити да ли постоје елементи који имају фреквенцију већу од ⌊Н / 3⌋. На тај начин можемо пронаћи све елементе који задовољавају услов.

Алгоритам

  1. Иницирајте ХасхМап-фреквенција за чување фреквенција елемената у низу и листе / вектора резултат за чување већинских елемената
  2. За сваки елемент у низу:
    • Повећајте његову учесталост: фреквенција [и] ++ (или поставити као 1 ако већ није присутан)
  3. За сваки кључ у хасхмапи:
    1. If фреквенција [тастер] > Н / 3
      1. Додајте га у резултат
  4. Врати списак резултат

Примена решења Леетцоде већине Елемента ИИ

Програм Ц ++

#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

Анализа сложености решења са већинским елементом ИИ са кодом

Сложеност времена

НА) док једном прелазимо читав низ да бисмо ажурирали фреквенције. N = величина низа.

Сложеност простора

НА) као што користимо хеш таблицу за чување фреквенција.

Приступ(Алгоритам гласања Боиер-Мооре-а)

Прво што овде треба приметити је да могу бити највише 2 елемента са фреквенцијом већом од ⌊Н / 3⌋ у низу. Дакле, овај проблем постаје исти као и Већински елемент проблем са 2 већински елементи овог пута.

Већ смо решили проблем већинског елемента помоћу Боиер-Мооре-овог алгоритма за гласање. У случају појединачног већинског елемента, могли бисмо да користимо алгоритам упоређивањем да ли је тренутни елемент кандидат или не. Али, у овом случају, морамо држати два потенцијална већинска елемента и паралелно ажурирати њихове бројаче. Уз помоћ ове интуиције можемо своје услове поставити на следећи начин:

  • Поставите било која два случајна кандидата изван опсега елемената у пољу.
  • Ако је елемент једнак било ком од кандидата, повећајте његов бројач.
  • Ако је бројач једног кандидата једнак 0 у било ком тренутку постављамо тренутни елемент као кандидата if овај тренутни елемент није други кандидат.
  • Умањујемо бројаче оба кандидата ако тренутни елемент није једнак ниједном од кандидата.

На овај начин настављамо да паралелно у низу одржавамо два различита кандидата, а да први кандидат не утиче на другог. Међутим, могуће је да кандидати код којих завршимо нису прави већински елементи ({1, 1, 2, 2, 3, 3} је један такав пример). Због тога је потребно извршити други пролаз да бисмо пребројали фреквенције кандидата са којима смо завршили. На основу овога можемо вратити вектор већинских елемената.

Алгоритам

  1. Инитиализе цандОне цандтво за чување два кандидата и њихових фреквенција цнтОне цнтТво as 0.
  2. За сваки елемент у низу:
    • If цандОне == и:
      • цнтОне++
    • ако не цандТво == i
      • цнтТво++
    • иначе ако цнједно == 0
      • Додели i as цандОне: цандОне = и
      • Поставите број 1: цнтОне = 1
    • ако не цнтТво == 0
      • цандТво = и
      • цнтТво = 1
    • Бројеви смањења оба кандидата:
      • цнтОне–
      • цнтТво–
  3. Вратите њихов број на нулу за други пролазак: цнтОне = 0 цнтТво = 0
  4. За сваки елемент у низу:
    • ако је једнако цандОне:
      • цнтОне ++
    • иначе ако је једнако цандТво:
      • цнтТво ++
  5. Иницијализујте листу / вектор резултат за чување већинских елемената
  6. Ако је цнтОне> Н / 3
    • гурање цандОне до резултат
  7. Ако је цнтТво> Н / 3
    • гурање цандТво до резултат
  8. Одштампајте резултат

Илустрација:

Решење Леетцоде већине Елемент ИИ

Примена решења Леетцоде већине Елемента ИИ

Програм Ц ++

#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

Анализа сложености решења са већинским елементом ИИ са кодом

Сложеност времена

НА) док изводимо два пролаза низа без обзира на улаз. N = величина низа.

Сложеност простора

О (1) како константно памтимо простор.