У вас есть массив A с n изображениями в формате JPEG, некоторые из которых идентичны.
Вы можете проверить, равны ли два объекта, но вы не можете сравнить их каким-либо другим способом, т.е. вы можете проверить A[i] == A[j] и A[i] != A[j], но такие сравнения, как A[i] ‹ A[j], не имеют смысла.
Говорят, что массив A имеет мажоритарный элемент, если строго более половины его элементов равны между собой.
Используйте разделяй и властвуй, чтобы придумать алгоритм O (n logn ), чтобы определить, имеет ли A элемент большинства.
................................................................................
Мое решение: я решил эту проблему, разделив массив изображений на половины, пока не появятся массивы размера 1 или 2.
Если массив имеет размер один, мы возвращаем элемент, присутствующий в этом массиве, а если он имеет размер два, мы сравниваем элементы массива. Если они одинаковы, мы возвращаем этот элемент, иначе он не возвращается.
Двигаясь рекурсивно вверх по дереву, мы выполняем те же операции над возвращенными элементами, пока не останется только один возвращенный элемент.
Мне было бы проще объяснить на примере
Предположим, что массив ABABAABA
ШАГ 1 Делим на половинки
[ABAB][AABA] -> [AB][AB][AA][BA]
Теперь [AB] ничего не возвращает (поскольку A отличается от B)
[AB] returns nothing
[AA] returns A
[BA] returns nothing
Таким образом, единственным возвращаемым элементом является A, который является элементом большинства. Теперь моя проблема в том, что вы обнаружите, что приведенный выше алгоритм не будет работать для многих массивов, таких как AAAAABBB, но я думаю, что это не работает только потому, что порядок перетасовки массива A и B устранит проблему. Скажите, пожалуйста, я прав?
И если мой алгоритм совершенно неверен, пожалуйста, дайте решение.
