Как найти элемент массива, который повторяется как минимум N / 2 раза?

Question

Дан массив с N элементами.Мы знаем, что один из этих элементов повторяется как минимум N / 2 раза.

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

Есть ли способ узнать элемент, который повторяется по крайней мере N / 2 раза за один проход или может быть O (N)?

Не нужно использовать дополнительное пространство.

Answer 1

Поскольку другие пользователи уже опубликовали алгоритм, я не буду повторять это.Однако я привожу простое объяснение того, почему это работает:

Рассмотрим следующую диаграмму, которая на самом деле является диаграммой неполяризованного света:

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

Answer 2

st0le ответил на вопрос, но вот 5-минутная реализация:

#include <stdio.h>

#define SIZE 13

int boyerMoore(int arr[]) {
    int current_candidate = arr[0], counter = 0, i;
    for (i = 0; i < SIZE; ++i) {
        if (current_candidate == arr[i]) {
            ++counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        } else if (counter == 0) {
            current_candidate = arr[i];
            ++counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        } else {
            --counter;
            printf("candidate: %i, counter: %i\n",current_candidate,counter);
        }
    }
    return current_candidate;
}

int main() {
    int numbers[SIZE] = {5,5,5,3,3,1,1,3,3,3,1,3,3};
    printf("majority: %i\n", boyerMoore(numbers));
    return 0;
}

А вот забавное объяснение (по крайней мере, веселее, чем читать газету): http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

Answer 3

Алгоритм голосования большинства Бойера-Мура

//list needs to have an element with a count of more than n/2 throughout itself for
//this algorithm to work properly at all times.

lst = [1,2,1,2,3,1,3,3,1,2,1,1,1]

currentCount = 0
currentValue = lst[0]
for val in lst:
   if val == currentValue:
      currentCount += 1
   else:
      currentCount -= 1

   if currentCount == 0:
      currentValue = val
      currentCount = 1


print(currentValue)

Answer 4

Этот код аналогичен реализации, в которой мы находим большинство элементов

int find(int* arr, int size)
{ 
int count = 0, i, m;
  for (i = 0; i < size; i++) 
  {
    if (count == 0)
        m = arr[i];
    if (arr[i] == m) 
        count++;
    else
        count--;
   }
    return m;
}

Answer 5

Попробуйте это:

#include<iostream>
using namespace std;
int main()
{
    int counter=0;
    int a[]={10, 11, 5, 27, 4, 2, 7, 5, 7, 11, 9, 5, 5, 4, 10, 7, 5, 3, 7, 5};
    for(int i = 0; i < 20; i++)
    {
        if(a[i]==5)
        counter++;
    }
    cout << "it appears " << counter << " times";
}

Answer 6

Используя модификацию, предложенную ffao для Davi'd, ответьте:

public class MaxRepeated {

    public static void main(final String[] args) {
        maxRepeatedElement(new int[]{1, 2, 1, 2, 3, 2, 3, 1});
        maxRepeatedElement(new int[]{1, 2, 1, 2, 3, 1, 3, 1});
        maxRepeatedElement(new int[]{1, 2, 1, 2, 4, 1, 1, 3, 1, 3, 1});
        maxRepeatedElement(new int[]{1, 2, 1, 2, 2, 1, 2, 3, 1, 2, 1, 2});
    }

    private static int maxRepeatedElement(final int[] arr) {

        int current_candidate = arr[0];
        int previous_candidate = arr[0];
        int counter = 0, i;
        for (i = 0; i < arr.length; ++i) {
            if (current_candidate == arr[i]) {
                ++counter;
            } else if (counter == 0) {
                previous_candidate = current_candidate;
                current_candidate = arr[i];
                ++counter;
            } else {
                --counter;
            }
            System.out.printf("  candidate: %d, counter: %d\n", current_candidate, counter);
        }

        if (counter == 0) {
            System.out.printf(" possible: %d or %d with net freq %d \n", current_candidate, previous_candidate, counter);
            final int f1 = frequency(arr, current_candidate);
            final int f2 = frequency(arr, previous_candidate);
            final int halfLen = arr.length / 2 + (arr.length % 2 == 0 ? 0 : 1);
            if (f1 >= halfLen || f2 >= halfLen) {
                if (f1 > f2) {
                    System.out.printf("majority: %d with freq %d \n", current_candidate, f1);
                } else {
                    System.out.printf("majority: %d with freq %d \n", previous_candidate, f2);
                }
            } else {
                System.out.printf("NO majority! \n");
            }
        } else {
            System.out.printf("majority: %d with freq %d \n", current_candidate, frequency(arr, current_candidate));
        }
        return current_candidate;
    }

    private static int frequency(final int[] arr, final int candidate) {
        int counter = 0;
        for (int c : arr) {
            counter += candidate == c ? 1 : 0;
        }
        return counter;
    }
}

Answer 7

Алгоритм голосования большинства Бойера-Мура не может найти правильное большинство в следующих входных массивах

int числа [РАЗМЕР] = {1,2,3,4,1,2, 3,4,1,2,3,4};

int числа [РАЗМЕР] = {1,2,3,4,1,2,3,4,1,2,3,4, 1};

Answer 8

Кажется невозможным считать что-либо без использования дополнительного пространства.Вы должны хранить хотя бы один счетчик где-то.Если вы хотите сказать, что не можете использовать больше, чем O (n) пробел, то это должно быть довольно просто.

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

Другим способом будет сортировка списка, а затем поиск наибольшего непрерывного раздела.