Решение Majority Element II Leetcode


Сложный уровень средний
Часто спрашивают в саман Амазонка Apple Bloomberg Facebook Google Microsoft Zenefits
массив

В этой задаче нам дается массив целых чисел. Цель состоит в том, чтобы найти все элементы, встречающиеся более чем ⌊N / 3⌋ время в массиве, где N = размер массива, а ⌊ ⌋ - оператор пола. Нам нужно вернуть массив таких элементов.

Ассортимент элементов: -10 ^ 9 в 10 ^ 9

Пример

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

объяснение⌊N / 3⌋ = ⌊5 / 3⌋ = 1. Теперь целые числа 2 и 3 имеют частоты, равные 2, что больше 1. Итак, печатаем их.

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

Объяснение: Мы не нашли ни одного элемента, частота которого в данном случае больше единицы. Итак, печатаем «Элементы без большинства».

Подход (сохранение частот)

Как следует из названия, мы можем сохранить частоту каждого элемента в массиве с помощью хеш-таблицы, а затем проверить элементы, частота которых превышает ⌊N / 3⌋. Таким образом, мы можем найти все элементы, удовлетворяющие условию.

Алгоритм

  1. Инициализировать HashMap-частота для хранения частот элементов в массиве и списке / векторе результат хранить большинство элементов
  2. Для каждого элемента в массиве:
    • Увеличьте его частоту: частота [i] ++ (или установить как 1, если еще нет)
  3. Для каждого ключ в хэш-карте:
    1. If частота [ключ] > N / 3
      1. Добавьте его в результат
  4. Вернуть список результат

Внедрение решения Majority Element II 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

Анализ сложности решения Leetcode для большинства элементов II

Сложность времени

НА) поскольку мы обходим весь массив один раз, чтобы обновить частоты. N = размер массива.

Космическая сложность

НА) поскольку мы используем хеш-таблицу для хранения частот.

Подход(Алгоритм голосования Бойера-Мура)

Первое, на что следует обратить внимание, это то, что может быть максимум 2 элемента с частотой больше, чем ⌊N / 3⌋ в массиве. Итак, эта проблема становится такой же, как и Элемент большинства проблема с 2 на этот раз большинство элементов.

Мы уже решили проблему большинства элементов, используя алгоритм голосования Бойера-Мура. В случае единственного мажоритарного элемента мы могли бы использовать алгоритм, сравнивая, является ли текущий элемент кандидатом. Но в этом случае нам нужно удерживать два потенциальных мажоритарных элемента и обновлять их счетчики параллельно. С помощью этой интуиции мы можем установить наши условия следующим образом:

  • Установите любые два случайных кандидата вне диапазона элементов в массиве.
  • Если элемент равен любому из кандидатов, увеличьте его счетчик.
  • Если счетчик одного кандидата равен 0 в любой момент мы устанавливаем текущий элемент в качестве кандидата if этот текущий элемент не является другим кандидатом.
  • Мы уменьшаем счетчики обоих кандидатов, если текущий элемент не равен ни одному из кандидатов.

Таким образом, мы продолжаем поддерживать двух разных кандидатов параллельно в массиве, при этом первый кандидат не влияет на другого. Однако возможно, что кандидаты, которые у нас в итоге окажутся, не являются истинными элементами большинства ({1, 1, 2, 2, 3, 3} - один из таких примеров). Следовательно, необходимо выполнить второй проход, чтобы подсчитать частоты кандидатов, которые у нас в итоге окажутся. На основе этого мы можем вернуть вектор мажоритарных элементов.

Алгоритм

  1. инициализировать CandOne и Candtwo для хранения двух кандидатов и их частот cntOne и cntTwo as 0.
  2. Для каждого элемента в массиве:
    • If CandOne == я:
      • cntOne++
    • Иначе, если CandTwo == i
      • cntTwo++
    • иначе если спtOne == 0
      • Назначать i as CandOne: CandOne = я
      • Установите его количество как 1: cntOne = 1
    • Иначе, если cntTwo == 0
      • candTwo = я
      • 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. Распечатать результат

Иллюстрация:

Решение Majority Element II Leetcode

Внедрение решения Majority Element II 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

Анализ сложности решения Leetcode для большинства элементов II

Сложность времени

НА) поскольку мы выполняем два прохода массива независимо от ввода. N = размер массива.

Космическая сложность

O (1) поскольку у нас постоянная память.