Аксарияти унсури II Solution Leetcode


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Adobe Amazon себ Блумберг Facebook Google Microsoft Zenefits
тартиботи ҳарбӣ

Дар ин масъала, ба мо як асал ададҳо. Мақсад он аст, ки ҳамаи унсурҳое пайдо шаванд, ки бештар аз он рух медиҳанд ⌊N / 3⌋ вақт дар массиве, ки N = андозаи массив ва ⌊ operator оператори ошёна аст. Мо бояд як қатор чунин унсурҳоро баргардонем.

Диапазони элементҳо: -10 ^ 9 ба 10 ^ 9

мисол

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

Шарҳ⌊N / 3⌋ = ⌊5 / 3⌋ = 1. Ҳоло ададҳои бутун 2 ва 3 басомади ба 2 баробар доранд, ки бузургтар аст. Ҳамин тавр, мо онҳоро чоп мекунем.

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

Шарҳ: Мо ягон унсуреро надидем, ки басомади он дар ин ҳолат аз 1 зиёд бошад. Ҳамин тавр, мо "Не унсурҳои аксарият" -ро чоп мекунем.

Равиш (басомади нигоҳдорӣ)

Тавре ки аз сарлавҳа бармеояд, мо метавонем басомади ҳар як унсурро дар массив бо истифода аз ҷадвали хэш нигоҳ дорем ва пас унсурҳои басомади калонтарро тафтиш кунем ⌊N / 3⌋. Бо ин роҳ, мо метавонем ҳамаи унсурҳои мувофиқи шартро пайдо кунем.

Алгоритм

  1. HashMap- ро оғоз кунедбасомад барои нигоҳ доштани басомади элементҳо дар массив ва рӯйхат / вектор натиҷа барои нигоҳ доштани унсурҳои аксарият
  2. Барои ҳар як унсур дар массив:
    • Афзоиши басомади он: басомади [i] ++ (ё ба андозаи 1 муқаррар карда шудааст, агар мавҷуд набошад)
  3. Барои ҳар як калид дар hashmap:
    1. If басомад [калид] > N / 3
      1. Онро ба натиҷа
  4. Рӯйхатро баргардонед натиҷа

Татбиқи аксарияти унсури II Solution 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 Leetcode Solution

Мураккабии вақт

О (Н) чунон ки мо тамоми массивро як маротиба тай карда, басомадҳоро навсозӣ мекунем. N = андозаи массив.

Мураккабии фазо

О (Н) чунон ки мо барои нигоҳ доштани басомадҳо ҷадвали хэшро истифода мебарем.

Равиш (Алгоритми овоздиҳии Бойер-Мур)

Аввалин чизе, ки дар инҷо мушоҳида мешавад, ин аст, ки ҳадди аксар 2 унсури дорои басомади калонтар вуҷуд дошта метавонанд ⌊N / 3⌋ дар массив. Пас, ин мушкил ҳамон тавре мешавад, ки Аксарияти унсур мушкилот бо 2 унсурҳои аксарият ин дафъа.

Мо аллакай бо истифода аз алгоритми овоздиҳии Бойер-Мур мушкилоти аксарияти элементро ҳал кардем. Дар сурати унсури аксарияти ягона, мо метавонистем алгоритмро бо муқоисаи номзад ё унсури ҳозира истифода барем. Аммо, дар ин ҳолат, мо бояд ду унсури эҳтимолии аксариятро нигоҳ дорем ва ҳисобкунакҳои онҳоро мувозӣ нав кунем. Бо ёрии ин ҳисси худ мо метавонем шароити худро ба таври зерин муқаррар кунем:

  • Ду номзади тасодуфиро берун аз доираи унсурҳои массив таъин кунед.
  • Агар унсур ба ҳарду номзад баробар бошад, ҳисобкунаки онро зиёд кунед.
  • Агар ҳисобкунии як номзад ба 0 дар ҳар лаҳза, мо унсури ҷориро ҳамчун номзад муқаррар кардем if ин унсури ҷорӣ номзади дигар нест.
  • Мо ҳисобкунакҳои ҳарду номзадро коҳиш медиҳем, агар унсури ҳозира ба ҳарду номзад баробар набошад.

Бо ин роҳ, мо нигоҳ доштани ду номзади мухталифро дар массив бидуни номзади аввал ба дигаре таъсир расониданро давом медиҳем. Аммо, ин имконпазир аст, ки номзадҳое, ки мо бо онҳо тамом мешавем, унсурҳои ҳақиқии аксарият набошанд ({1, 1, 2, 2, 3, 3} яке аз чунин мисолҳо аст). Аз ин рӯ, зарур аст, ки гузариши дуввумро барои ҳисоб кардани басомади номзадҳо, ки мо бо он анҷом меёбем, гузаронидан лозим аст. Дар асоси ин, мо метавонем вектори унсурҳои аксариятро баргардонем.

Алгоритм

  1. Оғоз candOne ва кандтво барои нигоҳ доштани ду номзад ва басомади онҳо cntOne ва cntTwo as 0.
  2. Барои ҳар як унсур дар массив:
    • If candOne == i:
      • cntOne++
    • дигаре агар candTwo == i
      • cntTwo++
    • дигаре агар cntOne == 0
      • Таъиншуда i as candOne: candOne = i
      • Ҳисоби онро ҳамчун 1 таъин кунед: cntOne = 1
    • дигаре агар cntTwo == 0
      • candTwo = i
      • cntTwo = 1
    • Ҳисобкунии коҳиши ҳарду номзад:
      • cntOne–
      • cntTwo–
  3. Ҳисоби онҳоро барои гузариши дуюм ба сифр баргардонед: cntOne = 0 ва cntTwo = 0
  4. Барои ҳар як унсури массив:
    • агар он ба candOne баробар бошад:
      • cntOne ++
    • дигаре агар он ба candTwo баробар бошад:
      • cntTwo ++
  5. Рӯйхат / векторро оғоз кунед натиҷа унсурҳои аксариятро нигоҳ доранд
  6. Агар cntOne> N / 3
    • Тела candOne ба натиҷа
  7. Агар cntTwo> N / 3
    • Тела candTwo ба натиҷа
  8. Натиҷаро чоп кунед

Сурат:

Аксарияти унсури II Solution Leetcode

Татбиқи аксарияти унсури II Solution 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 Leetcode Solution

Мураккабии вақт

О (Н) чунон ки мо ду гузариши массивро сарфи назар аз вуруд иҷро мекунем. N = андозаи массив.

Мураккабии фазо

О (1) чунон ки мо фазои хотира доимо.