Сложность: medium
Дан отсортированный массив, состоящий только из целых чисел, где каждый элемент встречается ровно дважды, кроме одного элемента, который встречается ровно один раз.
Верните единственный элемент, который встречается только один раз.
Ваше решение должно работать за время O(log n) и использовать O(1) памяти.
Пример:
Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2
👨💻 Алгоритм:
1⃣Начиная с первого элемента, итерируемся через каждый второй элемент, проверяя, является ли следующий элемент таким же, как текущий. Если нет, то текущий элемент — это искомый элемент.
2⃣Если доходим до последнего элемента, то он является искомым элементом. Обрабатываем этот случай после завершения цикла, чтобы избежать выхода за пределы массива.
3⃣Возвращаем найденный элемент.
😎 Решение:
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
for i in range(0, len(nums) - 1, 2):
if nums[i] != nums[i + 1]:
return nums[i]
return nums[-1]
Ставь 👍 и забирай 📚 Базу знаний