Daily bit(e) C++. Поиск одиночного числа

Добавлено 17 сентября 2023 в 18:18

Daily bit(e) C++ #219, распространенная задача на собеседованиях: поиск одиночного числа.

Сегодня мы рассмотрим распространенную задачу на собеседованиях по C++: поиск одиночного числа.

Дан отсортированный массив целых чисел в виде std::vector<int>, где все значения присутствуют дважды, за исключением одного одиночного числа, верните это одиночное число.

Ваше решение должно работать со сложностью O(logn) и использовать память O(1).

Например, для входных данных {1,1,4,4,5,5,7,9,9} результат равен 7.

Прежде чем прочитать решение, советую попытаться решить задачу самостоятельно. Вот ссылка на Compiler Explorer с парой тестовых случаев: https://compiler-explorer.com/z/q6GbnEK1Y.

Решение

Во-первых, давайте рассмотрим, что значит иметь отсортированный массив, в котором все значения, кроме одного, дублируются.

У нас будет ведущая (потенциально пустая) последовательность значений, занимающая индексы 2*n и 2*n+1, после чего у нас будет наше одиночное число, которое также будет занимать четный индекс (2*n), сдвигая все последующие пары чисел на единицу.

Поэтому мы можем переформулировать нашу цель. Мы ищем значение n, которое соответствует положению одиночного числа, или, точнее, минимальное n, для которого value[2*n] != value[2*n+1].

Это дает нам простой бинарный поиск по n, начиная с левой границы, установленной в ноль, и правой границы, установленной в size()/2.

int singular_value(const std::vector<int>& nums) 
{
    int64_t left = 0;
    int64_t right = nums.size()/2;
    while (left != right) 
    {
        int64_t mid = std::midpoint(left, right);
        if (nums[2*mid] == nums[2*mid+1])
            left = mid+1;
        else
            right = mid;
    }
    return nums[2*left];
}

Открыть решение на Compiler Explorer.

Или, что более правильно, без повторной реализации существующих алгоритмов.

int singular_value_proper(const std::vector<int>& nums) 
{
    int64_t idx = *std::ranges::partition_point(
        // Важно, мы должны пройти только: 0..size()/2-1
        std::views::iota(int64_t{0}, std::ssize(nums)/2),
        [&](int64_t n) {
            return nums[2*n] == nums[2*n+1];
        });
    return nums[2*idx];
}

Открыть решение на Compiler Explorer.

Решение

Теги