По заданному несортированному массиву целых чисел найти числа, которые нельзя найти

Question

Интервью с другом

Если не отсортированный целочисленный массив, сколько чисел не удается найти с помощью бинарного поиска?

Например, [2, 3, 4, 1,5], только число 1 не может быть найдено с помощью бинарного поиска, следовательно, count = 1

[4,2,1,3,5] 4 и 4 и 2 не доступны для поиска => binarySearch (arr, n) вернуть число, которое не равно num

Ожидаемое время выполнения O (n)

Не могу придумать алгоритм, который может достичь O (n) времени: (

Мысль о построении минимального и максимального значения arr, однако, не будет работать, поскольку подмассив может снова его испортить.

Уже знал подход O (nlogn), это было очевидно, просто вызов двоичного коданайдите каждый номер и проверьте.

Answer 1

Я считаю, что этот код работает нормально.Он выполняет один обход каждого значения в списке, поэтому это O (n).

function CountUnsearchable(list, minValue = -Infinity, maxValue=Infinity) {
  if (list is empty) return 0;
  let midPoint = mid point of "list"
  let lowerCount = CountUnsearchable(left half of list, minValue, min(midPoint, maxValue));
  let upperCount = CountUnsearchable(right half of list, max(minValue, midPoint), maxValue);
  let midPointUnsearchable = 1 if midPoint less than minValue or greater than maxValue, otherwise 0;
  return lowerCount + upperCount + midPointUnsearchable;
}

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

Answer 2

Попробуйте создать следующую функцию:

def count_unsearchable(some_list, min_index=None, max_index=None, min_value=None, max_value=None):
    """How many elements of some_list are not searchable in the
       range from min_index to max_index, assuming that by the time
       we arrive our values are known to be in the range from
       min_value to max_value.  In all cases None means unbounded."""
    pass #implementation TBD

Эту функцию можно реализовать способом, который выполняется во времени O(n).Причина, по которой он быстрее, чем наивный подход, заключается в том, что вы делаете рекурсивные вызовы только один раз для каждого диапазона, а не один раз для каждого элемента в этом диапазоне.