Найти элемент большинства в массиве

Question

Мажоритарный элемент - это элемент, размер которого превышает половину массива.

Как найти мажоритарный элемент в массиве в O(n)?

Пример ввода:

{2,1,2,3,4,2,1,2,2}

Ожидаемый результат:

2

Answer 1

// returns -1 if there is no element that is the majority element, otherwise that element

// funda :: if there is a majority element in an array, say x, then it is okay to discard 
// a part of that array that has no majority element, the remaining array will still have
// x as the majority element

// worst case complexity :  O(n)

int findMajorityElement(int* arr, int size) { 
    int count = 0, i, majorityElement;
    for (i = 0; i < size; i++) {
        if (count == 0)
            majorityElement = arr[i];
        if (arr[i] == majorityElement) 
            count++;
        else
            count--;
    }
    count = 0;
    for (i = 0; i < size; i++)
        if (arr[i] == majorityElement)
            count++;
    if (count > size/2)
        return majorityElement;
    return -1;
}

Answer 2

Печально видеть, что за 5 лет никто не написал надлежащего объяснения этой проблемы.

Это стандартная проблема в алгоритмах потоковой передачи (где у вас огромный (потенциально бесконечный) поток данных) и вам нужно вычислить некоторую статистику из этого потока, проходящего через этот поток один раз.

---

Очевидно, что вы можете обратиться к нему с помощью хеширования или сортировки, но с потенциально бесконечным потоком вы можете явно исчерпать память,Таким образом, вы должны сделать что-то умное здесь.

---

Мажоритарный элемент - это элемент, размер которого превышает половину размера массива .Это означает, что мажоритарный элемент встречается чаще, чем все остальные элементы вместе взятые.То есть, если вы посчитаете, сколько раз появляется элемент контрольного числа, и вычтете количество вхождений всех других элементов, вы получите положительное число.

Так что, если вы посчитаете вхождения некоторого элемента,и вычтите количество вхождений всех других элементов и получите число 0 - тогда ваш исходный элемент не может быть элементом большинства.Это основа для правильного алгоритма:

Объявите две переменные, counter и возможных_элементов.Повторяйте поток, если счетчик равен 0 - перезаписать возможный элемент и инициализировать счетчик, если число совпадает с возможным элементом - увеличить счетчик, в противном случае уменьшить его. Код Python:

def majority_element(arr):
    counter, possible_element = 0, None
    for i in arr:
        if counter == 0:
            possible_element, counter = i, 1
        elif i == possible_element:
            counter += 1
        else:
            counter -= 1

    return possible_element

Ясно, что алгоритм равен O(n) с очень маленькой константой до O(n) (например, 3).Также похоже, что сложность пространства равна O(1), потому что у нас только три инициализированные переменные.Проблема в том, что одна из этих переменных является счетчиком, который потенциально может вырасти до n (когда массив состоит из одинаковых чисел).А для хранения числа n нужно O(log (n)) пробела.Так что с теоретической точки зрения это O(n) время и O(log(n)) пространство. Из практического вы можете поместить 2 ^ 128 в длинную строку, и это количество элементов в массиве невообразимо огромно.

Также обратите внимание, что алгоритм работает только при наличии элемента большинства,Если такого элемента не существует, он все равно вернет некоторое число, что, несомненно, будет неправильным.(легко изменить алгоритм, чтобы определить, существует ли элемент большинства)

Канал истории: этот алгоритм был изобретен где-то в 1982 году Бойером, Муром и назван Алгоритмом большинства голосов Бойера-Мура

Answer 3

Элемент большинства (если он существует) также будет медианой. Мы можем найти медиану в O (n) и затем проверить, что она действительно является допустимым мажоритарным элементом в O (n). Подробнее о реализации ссылка

Answer 4

Элемент большинства:

Элемент большинства в массиве A [] размера n - это элемент, который появляется более чем в n / 2 раза (и, следовательно, существует не более одного такогоelement).

Поиск кандидата:

Алгоритм первой фазы, который работает в O (n), известен как алгоритм голосования Мура.Основная идея алгоритма состоит в том, что если мы отменяем каждое вхождение элемента e со всеми другими элементами, отличными от e, то e будет существовать до конца, если он является мажоритарным элементом.

findCandidate(a[], size)
1.  Initialize index and count of majority element
     maj_index = 0, count = 1
2.  Loop for i = 1 to size – 1
    (a)If a[maj_index] == a[i]
        count++
    (b)Else
        count--;
    (c)If count == 0
        maj_index = i;
        count = 1
3.  Return a[maj_index]

Выше алгоритмациклически проходит по каждому элементу и поддерживает счетчик [maj_index]. Если следующий элемент такой же, то увеличивает счетчик, если следующий элемент не совпадает, то уменьшает счетчик, а если счет достигает 0, то меняет maj_index на текущий элементустанавливает количество в 1. Алгоритм первой фазы дает нам элемент-кандидат.На втором этапе нам нужно проверить, действительно ли кандидат является мажоритарным элементом.

Второй этап прост и может быть легко выполнен за O (n).Нам просто нужно проверить, больше ли количество элементов-кандидатов, чем n / 2.

Читать geeksforgeeks для более подробной информации

Answer 5

Время: O (n)

Пробел: O (n)

Прогулка по дереву и подсчет появления элементов в хеш-таблице.

Время: O(n lg n) или O (n * m) (зависит от используемой сортировки)

пробел: (1)

сортировка массива и подсчет вхождений элементов.

Правильный ответ на собеседование: алгоритм голосования Мура

Время: O (n)

Пробел: O (1)

Пройдите по списку, сравните текущее число с текущим лучшимугадай числоЕсли число равно текущему номеру наилучшего предположения, увеличьте счетчик, в противном случае уменьшите счетчик, а если счетчик достигнет нуля, замените текущее число наилучшего предположения текущим числом и установите счетчик на 1. Когда вы достигнете конца, текущийЛучшее предположение - номер Кандидата, пройдитесь по списку еще раз, просто посчитав экземпляры кандидата.Если окончательный счет больше n / 2, то это номер большинства, иначе его нет.

Answer 6

Как насчет подхода случайной выборки? Вы можете выбрать, скажем, элементы sqrt (n), и для каждого элемента, который встречался более чем в sqrt (n) / 4 раза (может быть выполнено наивно за время O (n) и пространство O (sqrt (n))), вы можете проверить было ли это мажоритарным элементом за O (n) раз.

Этот метод находит большинство с высокой вероятностью, потому что элемент мажорита будет отбираться как минимум в sqrt (n) / 2 раза в ожидании со стандартным отклонением не более n ^ {1/4} / 2.

Другой подход к выборке, который похож на подход, который я видел в одной из дублирующих ссылок, состоит в том, чтобы нарисовать две выборки, и, если они равны, проверьте, что вы нашли мажоритарный элемент за O (n) времени. Необходим дополнительный шаг проверки, потому что другие элементы, кроме большинства, могут не различаться.

Answer 7

В алгоритме Монте-Карло,

Majority (a,n)
//a[]-array of 'n' natural numbers
 {
  j=random(0,1,....,n-1)
  /*Selecting the integers at random ranging from 0 to n-1*/
  b=a[j];c=0;
  for k from 0 to n-1 do
   { 
    if a[k]=b then,
    c=c+1;
    }
    return (c>n/2)
   }

Answer 8

Чтобы найти большинство элементов в массиве, вы можете использовать алгоритм голосования большинства Мура, который является одним из лучших алгоритмов для него.

Сложность времени: O(n) or linear time

Сложность пространства: O(1) or constant space

Подробнее на Алгоритм голосования большинства Мура и GeeksforGeeks

Answer 9

Используйте Разделяй и властвуй, чтобы найти элемент большинства. Если мы разделим массив на две половины, мажоритарный элемент должен быть большинством в одной из половин. Если мы пойдем дальше и скомбинируем вложенные массивы, мы сможем выяснить, является ли элемент контрольного пакета также большинством объединенного массива. Это имеет сложность O (nlogN).

Вот реализация C ++:

#include <algorithm>
#include <iostream>
#include <vector>

using std::vector;

// return the count of elem in the array
int count(vector <int> &a, int elem, int low, int high)
{
    if (elem == -1) {
        return -1;
    }

    int num = 0;
    for (int i = low; i <= high; i++) {
        if (a[i] == elem) {
            num++;
        }
    }

    return num;
}

// return the majority element of combined sub-array. If no majority return -1
int combined(vector <int> &a, int maj1, int maj2, int low, int mid, int high)
{
    // if both sub arrays have same majority elem then we can safely say
    // the entire array has same majority elem.
    // NOTE: No majority ie. -1 will be taken care too
    if (maj1 == maj2) {
        return maj1;
    }

    // Conflicting majorities
    if (maj1 != maj2) {
        // Find the count of each maj1 and maj2 in complete array
        int num_maj1 = count(a, maj1, low, high);
        int num_maj2 = count(a, maj2, low, high);
        if (num_maj1 == num_maj2) {
            return -1;
        }
        int half = (high - low + 1) / 2;
        if (num_maj1 > half) {
            return maj1;
        } else if (num_maj2 > half) {
            return maj2;
        }
    }
    return -1;
}

// Divide the array into 2 sub-arrays. If we have a majority element, then it
// should be a majority in at least one of the half. In combine step we will
// check if this majority element is majority of the combination of sub-arrays.
// array a and low is lower index and high is the higher index of array
int get_majority_elem(vector<int> &a, int low, int high)
{
  if (low > high) return -1;
  if (low == high) return a[low];

  int mid = (low + high) / 2;

  int h1 = get_majority_elem(a, low, mid);
  int h2 = get_majority_elem(a, mid + 1, high);

  // calculate the majority from combined sub arrays
  int me = combined(a, h1, h2, low, mid, high);
  return me;
}

Answer 10

Вот как я делаю это в C ++, используя vector и multimap (JSON с ключами повтора).