Divide and conquer - Plural Array

Question

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

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

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

Assume you have the array 

aaabbcac 

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

aa ab bc ac 

отсюда, я буду сравнивать каждый элемент в Подмассив, чтобы увидеть, если они равны: Если РАВНО, возвращает элемент, Иначе, вернуть ложь.

aa ab bc ac 
a f f f 

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

я думал комбинируя их таким образом:

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

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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