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


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon себ Atlassian Блумберг Facebook GoDaddy Google Microsoft Oracle фасли Snapchat Yahoo Zenefits
алгоритмҳо рамзгузорӣ Тақсим кунед ва ғолиб шавед Хашм мусоҳиба омодасозии мусоҳиба LeetCode LeetCodeSolutions

Изҳороти мушкилот  

Ба мо як асал ададҳо. Мо бояд ададеро, ки дар which operator оператори ошёна аст, бештар аз ⌊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⌋ осон мешавад.

Алгоритм

  1. Ҷадвали хэшро барои нигоҳ доштани басомади бутунҳо дар массив оғоз намоед: басомад
  2. Барои ҳар як унсур, i, дар массив:
    • Афзоиш басомад [ман] ё танзим басомад [i] = 0 агар он аллакай дар ҷадвал набошад
    •  If басомад [ман] > N / 2:
      • баргардам ман
  3. Бозгаштан -1 (барои роҳ надодан ба хатои тартиб)
  4. Натиҷаро чоп кунед

Татбиқи аксарияти унсури Solution Leetcode

Барномаи 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

Таҳлили мураккабии ҳалли аксарияти унсури Leetcode

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

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

ҳамчунин нигаред
Шумораи ҳадди ақали қадамҳо барои ҳалли ду сатри Анаграммаи Leetcode

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

О (Н) чунки шумораи максималии унсурҳои алоҳида дар массив инҳо буда метавонанд: N - ⌊N / 2⌋ чун унсури аксарият ҳадди аққал ишғол мекунад ⌊Н / 2⌋ нишондиҳандаҳо. Аз ин рӯ, мураккабии фазо хаттӣ аст.

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

Ин мушкилот мисоли хубест, ки чӣ гуна мо метавонем унсури аксариятро дар ҷараёни унсурҳо пайдо кунем. Алгоритми овоздиҳии Бойер-Мур барои пайдо кардани унсуре истифода мешавад, ки дар пайдарпаӣ зиёда аз ⌊N / 2⌋ ҷойро ишғол мекунад. Ин алгоритм a -ро нигоҳ медорад номзад ва он шумурдан дар массиви. Мо як гузариши массивро бо номзад = -1 ва шумурдан = 0. Агар ягон элементи массив он бошад номзад, мо афзоиш медиҳем ҳисоб. Дар акси ҳол, мо онро кам мекунем. Агар ҳисоб сифр шавад, мо тағиротро тағир медиҳем номзад ва онро таъин кунед шумурдан бозгашт ба 0.

Барои фаҳмидани фаъолияти он, ба намунаи зерин пайравӣ кунед:

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

Ин алгоритм равандро ҳамчун интихобот ҳисобида, аввал номзадро муайян мекунад. Касе, ки бештар овоз мегирад, номзадии аксарият мебошад. Дар мисоли дар боло овардашуда, мо номзадеро аввал 1 интихоб мекунем, аммо вақте ки ба индекси 4 дар массив расидем, мо ҳисоб = 0 -ро мушоҳида мекунем, ки ин маънои онро дорад, ки мо шумораи номзадҳоро ҳамчун номзадҳо дидаем. Ҳамин тавр, мо унсури ҷориро ҳамчун номзад интихоб карда, равандро идома медиҳем. Азбаски мо ҳастем кафолат дода мешавад ки дар массив унсури аксарият дошта бошад, охирин номзаде, ки боқӣ мондаем, унсури аксарият хоҳад буд.

Алгоритм

  1. Ду тағирёбандаро оғоз кунед: номзад ва cnt номзад ва басомади онро барои такрори мувофиқ нигоҳ дорад
  2. Ҳоло, барои ҳар як унсур i дар массив:
    • If cnt ба сифр баробар аст:
      • навсозӣ: номзад = ман
    • If i баробар аст номзад:
      • афзоиш cnt: cnt ++
    • Дигар:
      • Декор cnt: cnt -
  3. бозгашт номзад
  4. Натиҷаро чоп кунед
ҳамчунин нигаред
Ҷамъи унсурҳои такрорнашавандаро (алоҳида) дар массив пайдо кунед

Татбиқи аксарияти унсури Solution Leetcode

Барномаи 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

Таҳлили мураккабии ҳалли аксарияти унсури Leetcode

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

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

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

О (1) вақте ки мо фазои хотираи доимиро истифода мебарем.