Поиск элемента Majority в массиве

Question

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

Во-первых, найден элемент-кандидат (это более сложная часть). Этот кандидат является единственным элементом, который может быть элементом большинства. Второй шаг определяет, действительно ли этот кандидат является большинством. Это просто последовательный поиск по массиву. Чтобы найти кандидата в массиве A, сформируйте второй массив B. Затем сравните A1, A2. Если они равны, добавьте одну из них в B; в противном случае ничего не делать. Затем сравните A3 и A4. Опять же, если они равны, добавьте одну из них в B; в противном случае ничего не делать. Продолжайте таким образом, пока весь массив не будет прочитан. Затем рекурсивно найдите кандидата для B; это кандидат на A.

Я понял, что N четный, алгоритм работает нормально. Но что, если N нечетно? Как мы можем справиться с этим делом?

Answer 1

Я думаю, что ваш алгоритм не будет работать, когда N тоже. Я могу доказать это с помощью примера:

Рассмотрим массив из 8 элементов: 2,2,1,1,3,2,2,2. Теперь ваш массив B будет 2,1,2 по вашему утверждению. Если вы повторите вышеуказанный шаг еще раз. Кандидатов не будет. Но реальный ответ здесь - «2». Поэтому этот метод определенно неверен.

Эта проблема обсуждалась на Geeks для вундеркиндов. Я думаю, что это поможет вам:

http://www.geeksforgeeks.org/majority-element/

Answer 2

Большинство элементов:

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

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

Алгоритм первого этапа, который работает в 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.

Answer 3

алгоритм, который вы объяснили работает на следующей идее:

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

2. Если два элемента отличаются друг от друга, то эта конкретная пара не определяет победителя.

Пункт № 2 имеет решающее значение - предположим, что пара (A1, A2) содержит элемент большинства (А1) и другой элемент меньшинства (А2). Удалите эту пару. A1 остается большинством в остальной части массива.

Если вы поняли это объяснение, тогда вы понимаете, почему ничего не добавляется к B, когда элементы отличаются.

Порог алгоритма, относящийся к массиву, содержащему нечетное число элементов, будет следующим: добавьте нечетный элемент в B. Причина такая же, как и # 1: это может быть элемент большинства, и он должен быть включен в выход, чтобы быть уверенным, что его счет не потерян в процессе.

Во всяком случае, все это может быть сделано без другого массива B. Здесь вы можете найти гораздо более простой алгоритм: Finding a Majority Element in an Array

Answer 4

Вот три алгоритма, которые решают эту проблему:

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

2) Элемент most должен быть медианом массива, если он существует. Вычислите медиану, используя метод медианной пяти или любой другой алгоритм, и убедитесь, что он больше n/2.

3) Алгоритм Boyer and Moore (те же ребята, которые выполняли алгоритм сопоставления строк) выбирает первый элемент массива в качестве элемента-кандидата и присваивает счету 1, затем сканирует массив, добавляя 1 к счету если следующий элемент совпадает с текущим кандидатом, вычитает 1 из счетчика, если следующий элемент отличается от текущего кандидата и сбрасывает кандидата на следующий элемент массива со счетом 1, когда счет достигает 0. На в конце сканирования текущий кандидат является членом большинства, если большинство существует, поэтому требуется второе сканирование, чтобы подтвердить, что кандидат составляет большинство.

Я обсуждаю и реализую все три алгоритма на своем blog.

Answer 5

Большинство элемент массива А [] размера п является элементом, который выглядит более чем п/2 раза

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