Разделяй и властвуй - множественный массив

Question

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

Массив является множественным числом, если в массиве существует элемент x, если более половины массива совпадает с x.

Мне интересно, существует ли более эффективный алгоритм «разделяй и властвуй», который работает лучше, чем текущий, который у меня есть сейчас.

Assume you have the array

aaabbcac

я буду рекурсивно разбивать массив до тех пор, пока не получу подмассивы размером 2, как показано ниже.

aa ab bc ac

отсюда, я буду сравнивать каждый элемент в SUBARRAY, чтобы увидеть, равны ли они: Если EQUAL, вернуть элемент, В противном случае верните false.

aa ab bc ac 
a  f   f  f

так что теперь у меня есть массив элементов A и 3 ложных.

Я думал объединить их так:

a  f  f  f
  a     f  <----- combining a and f will give a
     a    <----- returns a

Но, если мы посмотрим на массив, у нас есть 4 A, что не соответствует критериям множественного массива. Он должен возвращать false, если массив не является множественным.

Я полагаю, что мой алгоритм будет работать в O (n lgn), если это будет правильный алгоритм, которого, к сожалению, нет.

Кто-нибудь может указать мне правильное направление для этого?

Answer 1

Вы также можете отсортировать массив с помощью некоторого алгоритма сортировки (например, быстрой сортировки), после этого цикла до элемента (N + 1) / 2, проверяя, совпадает ли элемент n + 1 с n. При использовании быстрой сортировки такой подход будет сложнее O(n*log n + n/2). Так что в основном мой алгоритм будет связан скоростью сортировки.

Answer 2

Поскольку это домашнее задание, вот подсказки - вы должны легко это доказать и закончить вопрос.

• Массив из одного элемента тривиально имеет множественный элемент
• Массив имеет не более одного множественного элемента, предположим, что он существует, и назовите его x.
• Если вы разделите массив на две половины, x будет множественным элементом как минимум одной из половин.

Answer 3

Это проблема подсчета количества вхождений x.Разбейте массив на вложенные массивы и отправьте x вместе с вложенными массивами.Возвращает count, sum count и проверяет, больше ли он размера массива.