Leetcode 540. Один элемент в отсортированном массиве

Leetcode 540. Один элемент в отсортированном массиве

Вопрос

Дан отсортированный массив, состоящий только из целых чисел, в котором каждый элемент встречается дважды, кроме одного элемента, который встречается один раз. Найдите этот единственный элемент, который появляется только один раз.

Пример 1:

Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Пример 2:

Input: [3,3,7,7,10,11,11]
Output: 10

Решение

Ввод дает отсортированный массив, поэтому одно число появится в первый раз nums[i] != num[i+1]

Время выполнения: 52 мс

# @param {Integer[]} nums
# @return {Integer}
def single_non_duplicate(nums)
    i = 0
    while i < nums.count
        return nums[i] if nums[i] != nums[i+1]
        i += 2
    end
end

И самый быстрый вариант, используйте bsearch:

Время выполнения:46 мс

# @param {Integer[]} nums 
# @return {Integer} 
def single_non_duplicate(nums)     
    nums[(0..nums.size).bsearch { |i| nums[i] != nums[i ^ 1] }] 
end