Решение вопроса кодирования № 1

Найти диапазон I

Учитывая отсортированный массив чисел, найдите первый диапазон чисел, который содержит цель. Диапазон содержит цель, если низкий ‹= целевой ‹= высокий. Если диапазон не существует, верните [-1, -1]

Пример:
Массив: [1, 2, 3, 4, 5, 6]
Цель: 4
Вывод: [3, 4]

Массив: [1, 2, 3, 4, 5, 6]
Цель: 0
Выход: [-1, -1]

Попробуйте, а затем вернитесь, если вы застряли или найдете решение.

Решение №1

Первое решение действительно прямолинейно, мы начинаем со второго элемента, и по мере прохождения массива мы проверяем, находится ли цель между предыдущим и текущим значением. Если в какой-то момент целевое значение находится между ними, мы возвращаем эти два числа. Однако, если число не найдено, мы возвращаем [-1, -1].

Код (С++)

pair<int, int> find_range(vector<int> arr, int target) {
   for(int i = 1; i < arr.size(); i++) {
      if(arr[i-1] <= target && arr[i] >= target)
         return {arr[i-1], arr[i]};
   }
   return {-1, -1};
}

Время: O(n)
Пространство: O(1)

Как видите, код прост и прямолинеен, а временная сложность не страшна, но мы можем сделать лучше.

Если вы получили вышеуказанное решение, вернитесь и перечитайте проблему и посмотрите, сможете ли вы улучшить свое решение. Как только вы это сделаете, вернитесь и посмотрите, как я это сделаю, и сравните ваше решение.

Решение №2

Если мы вернемся и перечитаем вопрос, мы найдем небольшой самородок, который поможет нам улучшить нашу временную сложность.

Дан отсортированный массив чисел

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

Код (С++)

pair<int, int> find_range(vector<int> arr, int target) {
  int low = 0, high = arr.size() - 1, mid;
    while(low <= high) {
      mid = (high + low) / 2;
      if(arr[mid] <= target && arr[mid + 1] >= target) {
        return {arr[mid], arr[mid+1]};
      } else if(arr[mid] < target) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  return {-1, -1};
}

Мы реализовали бинарный поиск, и это приводит к тому, что наше время достигает O(log n), но если мы вернемся и перечитаем вопрос, мы обнаружим, что не охватываем все случаи.

первый диапазон чисел, который содержит цель

Если мы запустим код, мы обнаружим, что он не покрывает его для следующего случая
arr = [0 1 1 1 1 1 1 1 1 1 1]
target = 1
expect = [0, 1]
факт = [1, 1]

Чтобы покрыть этот пограничный случай, нам нужно выполнить некоторые проверки, когда мы узнаем, что цель находится в пределах досягаемости. Если наш настоящий и следующий совпадают, то мы можем спокойно вернуться такими, какие мы есть. Если они совпадают и предыдущий и первый не совпадают возвращаем предыдущий и текущий. Если это не так, у нас высокий уровень будет средним — 1.

Код (С++)

if(arr[mid] != arr[mid + 1])
  return {arr[mid], arr[mid + 1]};
if(arr[mid - 1] != arr[mid] && arr[mid] == arr[mid + 1])
  return {arr[mid - 1], arr[mid]};
high = mid - 1;

Хорошо, это было не так уж плохо, чтобы пройти тест. Однако у нас все еще есть проблема в коде. Если мы получим массив максимального размера и будем искать значение больше последнего значения, произойдет переполнение. Чтобы решить эту проблему, мы делаем простое исправление: среднее = низкое + ((высокое — низкое) / 2). Сделав это, наше окончательное решение будет

Код (С++)

pair<int, int> find_range(vector<int> arr, int target) {
  int low = 0, high = arr.size() - 1, mid;
    while(low <= high) {
      mid = low + ((high - low) / 2);
      if(arr[mid] <= target && arr[mid + 1] >= target) {
        if(arr[mid] != arr[mid + 1])
          return {arr[mid], arr[mid + 1]};
        if(arr[mid - 1] != arr[mid] && arr[mid] == arr[mid + 1])
          return {arr[mid - 1], arr[mid]};
        high = mid - 1;
      } else if(arr[mid] < target) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  return {-1, -1};
}

Время: O(log n)

Пробел: O(1)

Надеюсь, вы нашли мое объяснение полезным и что вы узнали из него что-то.