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

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

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

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

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

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

 #include  #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

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

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

стрелки, исходящие из центра

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

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

 //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) 

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

 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; } 

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

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

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

Используя модификацию, предложенную 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; } } 

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

 #include 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"; } 

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

int numbers [SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4};

int numbers [SIZE] = {1,2,3,4,1,2,3,4,1,2,3,4,1};

  • Каковы различия между деревьями сегментов, деревьями интервалов, двоичными индексированными деревьями и деревьями диапазона?
  • Интервью: Объединение двух отсортированных односвязных списков
  • Как получить случайный элемент из контейнера C ++?
  • Обнаружение, если geolocation находится в сложном полигоне или нет
  • Рассчитайте, когда будет выполняться задание cron, а затем в следующий раз
  • Как конвертировать поплавки в читаемые человеком фракции?
  • Как проверить, является ли число мощностью 2
  • Случайный взвешенный выбор
  • Массив удаляет повторяющиеся элементы
  • Как найти факториал?
  • Lossless JPEG Rotate (90/180/270 gradleусов) в Java?
  • Давайте будем гением компьютера.