Дан отсортированный массив, состоящий только из целых чисел, в котором каждый элемент встречается дважды, кроме одного элемента, который встречается один раз. Найдите этот единственный элемент, который появляется только один раз.
Пример 1:
Input: [1,1,2,3,3,4,4,8,8] Output: 2
Пример 2:
Input: [3,3,7,7,10,11,11] Output: 10
Примечание. Ваше решение должно выполняться за O(log n) времени и O(1) пространства.
Решение:
Пояснение:
Я беру две точки i и j, которые будут последовательными элементами в данном массиве. Если в какой-либо позиции эти последовательные элементы не равны, то это означает, что первое такое вхождение является нужным нам элементом. Поскольку мы увеличиваем цикл на 2, он выполняется с временной сложностью O(log n). Если такой элемент не встречается, мы можем с уверенностью сказать, что последним элементом в отсортированном массиве является тот, у которого нет повторяющегося значения.
источник: Литкод
