Көпчүлүк элемент Leetcode чечими


Кыйынчылык деңгээли жеңил
Көп суралган Amazon алма Atlassian Bloomberg Facebook GoDaddy Гугл Microsoft Oracle бөлүм снэпчат Yahoo Zenefits
Бөлүп ал жана жең Hashing

Маселени билдирүү

Бизге ан согуштук тизме бүтүн сандар. Floor ⌋ кабат оператору болгон массивде ⌊N / 2⌋ убакыттан көп болгон бүтүн санды кайтарып беришибиз керек. Бул элемент көпчүлүк элемент деп аталат. Киргизүү массиви ар дайым көпчүлүк элементин камтый тургандыгын эске алыңыз.

мисал

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

Exaplanation: ⌊N / 2⌋ = 4/2 = 2. Ал эми '3' бүтүндөй массивде 3 жолу болот.

Array = {1 , 1 , 2}
1

түшүндүрүү: ⌊N / 2⌋ = ⌊3 / 2⌋ = 1. Жана '1' массивде 2 жолу кездешет.

Мамиле (Hashtable)

Массивдеги ар бир элементтин жыштыгын таштанды таблицасында сактай алабыз. Андан кийин> ⌊N / 2⌋ жыштыгына ээ бүтүн санды текшерүү оңой болуп калат.

Algorithm

  1. Массивдеги бүтүн сандардын жыштыгын сактоо үчүн хэш таблицасын баштаңыз: жыштыгы
  2. Ар бир элемент үчүн, i, массивде:
    • Көбөйтүү жыштык [i] же коюлган жыштык [i] = 0 эгер ал буга чейин таблицада жок болсо
    •  If жыштык [i] > N / 2:
      • кайтуу i
  3. Кайтаруу -1 (компиляция катасынан качуу үчүн)
  4. Жыйынтыгын басып чыгарыңыз

Көпчүлүк элемент 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 чечиминин татаалдыгын талдоо

Убакыт татаалдыгы

O (N) массивди бир жолу айланып өтүп, көпчүлүктүн элементин табабыз. N = массивдин көлөмү.

Космостун татаалдыгы

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

Мамиле (Бойер-Мур добуш берүү алгоритми)

Бул көйгөй элементтердин агымында көпчүлүк элементти кантип табууга боло тургандыгы жөнүндө сонун мисал. Бойер-Мур добуш берүү алгоритми ырааттуулукта ⌊N / 2⌋ орунду ээлеген элементти табуу үчүн колдонулат. Бул алгоритм а талапкер жана анын эсинде эсептөө массивде. Биз массивдин бир өтмөгүн иштетебиз талапкер = -1 жана эсептөө = 0. Эгерде массивдеги кандайдыр бир элемент талапкер, биз көбөйтөбүз эсептөө. Болбосо, биз аны азайтабыз. Эгерде эсептөө нөлгө айланса, анда биз өзгөртөбүз талапкер жана аны койду эсептөө артка 0.

Анын иштешин түшүнүү үчүн төмөндөгү мисалды аткарыңыз:

Көпчүлүк элемент Leetcode чечими

Бул алгоритм жараянды шайлоо катары карап, алгач талапкерди аныктайт. Эң көп добуш алган адам көпчүлүктүн талапкери. Жогорудагы мисалда биз талапкерди алгач 1 деп тандайбыз, бирок массивде 4 көрсөткүчкө жеткенде, санап жаткандыгыбызды = 0 байкайбыз, демек, биз талапкерлердин катарына кирбеген талапкерлердин санын көп көрдүк. Ошентип, учурдагы элементти талапкер катары тандап, процессти улантабыз. Биз болгондуктан кепилдик массивде көпчүлүк элементи болуш үчүн, биз калган акыркы талапкер көпчүлүк элемент болот.

Algorithm

  1. Эки өзгөрүлмө инициализация: талапкер жана CNT талапкерди жана анын жыштыгын тиешелүү кайталоолор үчүн сактоо
  2. Эми, ар бир элемент үчүн i массивде:
    • If CNT нөлгө барабар:
      • өзгөртүү: талапкер = i
    • If i болуп барабар талапкер:
      • көбөйтүү CNT: cnt ++
    • Башка:
      • Decrement CNT: cnt–
  3. Return талапкер
  4. Жыйынтыгын басып чыгарыңыз

Көпчүлүк элемент 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 чечиминин татаалдыгын талдоо

Убакыт татаалдыгы

O (N) биз бүтүндөй массивди бир жолу айланып өткөндө. Бул жерде, N = массивдин көлөмү.

Космостун татаалдыгы

O (1) биз туруктуу эс мейкиндигин колдонуп жатканда.