Ежедневный бит (е) 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 ] != значение[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(
// Important, we must go only over: 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];
}
