Дан массив из 2n элементов, из которых n похожи, а n разные.

Question

Дан массив из 2n элементов, из которых n элементов одинаковы, а остальные n элементов различны. Напишите программу на C, чтобы узнать значение, которое присутствует n раз в массиве

Я подумала так: сравнить [я] и [я + 1] и сравнить [я] и [я + 2] и вернуть элемент

это будет выполнено за O (n) время .. кто-нибудь может дать лучшее решение?

Я пытался найти решение, в котором говорится вот так:

1. Объявите две переменные a) переменную count, чтобы отслеживать количество элементов контрольного числа.
2. Элемент большинства.
3. Выполните цикл for и повторяйте шаги 4-6, пока не будет достигнут конец массива.
4. если текущий элемент массива равен мажоритарному элементу, счетчик приращений
5. иначе, если число равно 0, обновить мажоритарный элемент с текущим элементом массива и счетчиком приращений.
6. иначе, если счет не равен 0, то счетчик декремента.
7. Сделайте еще один цикл for и посчитайте количество вхождений элемента контрольного числа в массиве, если он равен половине размера массива, то мы нашли элемент контрольного числа, иначе элемент элемента контрольного набора отсутствует.

Answer 1

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

Вам нужно место для одного сохраненного элемента.Выберите первый элемент и сохраните его, если следующий элемент совпадает с сохраненным, вы закончили.Если нет, перезапустите алгоритм со следующего шага.Если вы не найдете элемент после его окончания, это означает, что элемент упорядочен в парах, таких как (a, b), (a, c), (a, d) или (b, a), (a, c), (a, d), (e, a) .. Сравните первые четыре элемента, и вы нашли дубликат.

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

Answer 2

Вот решение с не более чем двумя проходами и пробелом O (1) с использованием алгоритма большинства голосов с линейным временем (http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html)

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

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