Учитывая массив целых чисел, отсортированных в порядке возрастания, найдите начальную и конечную позиции заданного целевого значения.
Сложность выполнения вашего алгоритма должна быть порядка O (log n).
Если цель не найдена в массиве, верните [-1, -1].
Пример 1:
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Пример 2:
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
Это проблема с leetcode: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
Решение:
Подход 1:
Сложность времени: O (n)
Космическая сложность: O (1)
В этом подходе мы сначала возьмем две переменные firstIndex и lastIndex. Мы будем перебирать массив с самого начала. Найдя элемент target, мы обновим как firstIndex, так и lastIndex.
Теперь у нас есть первое вхождение, но нам все еще нужно найти последнее вхождение. Мы продолжим перебирать массив и обновлять lastIndex, пока не встретим элемент target.
Например, у нас есть массив [1,2,4,6,8,8,8,8,8,8,9,10,11], а цель - 8.
Теперь мы начнем итерацию с нулевого индекса. В четвертом индексе мы встретим 8, поэтому firstIndex будет 4, а lastIndex также будет 4. Теперь мы продолжим итерацию массива, и пока мы не встретим 8 в массиве, мы будем продолжать увеличивать lastIndex.
Ниже приведено решение этой проблемы на языке Java:
package com.ds.arrays; public class FirstAndLastPosition { public static int[] searchRange(int[] nums, int target) { int[] result = new int[2]; result[0] = -1; result[1] = -1; for (int i = 0; i < nums.length; i++) { if (nums[i] == target) { if (result[0] == -1) { result[0] = i; result[1] = i; } else { result[1] = i; } } } return result; } }
Проблема с этим подходом в том, что он очень медленный, если массив очень большой. Предположим, что в массиве 10000 элементов, в этом случае перебор всего массива займет много времени. Мы можем воспользоваться двоичным поиском, чтобы сократить время. Я расскажу об этом в следующем подходе.
Подход 2:
Сложность времени: O (log (n))
Космическая сложность: O (1)
Прежде чем я углублюсь в решение, позвольте мне кратко рассказать вам о бинарном поиске. Это важная концепция, и ее можно использовать для решения множества проблем, связанных с массивами. Если вы уже знакомы с бинарным поиском, это будет для вас быстрое исправление.
Работа бинарного поиска
Предположим, у меня есть отсортированный массив (помните, что двоичный поиск работает только для отсортированных массивов), который содержит 20 элементов.
int [] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
Теперь, если нам нужно найти 20 в этом массиве и мы используем линейный поиск, нам придется начинать с начала, пока мы не дойдем до конца и не найдем 20 в последней позиции. Таким образом, нам потребуется 20 сравнений, прежде чем мы получим наш результат.
Вместо этого в двоичном поиске мы продолжаем делить массив от середины, пока не найдем число. В приведенном выше примере число 20 можно найти только в 4 сравнениях. Ниже представлена работа бинарного поиска:
Изначально предположим, что у нас есть три переменные start, end и mid.
Формула для вычисления mid = start + ((end - start) / 2)
Сравнение 1: начало - 0, конец - 20, а середина - 10. nums [mid] равно 11, что равно ‹target (20), поэтому start станет mid + 1, то есть 11.
Сравнение 2: начало - 11, конец - 20, а середина - 15. nums [mid] равно 16, что равно ‹target (20), поэтому start станет mid + 1, то есть 16.
Сравнение 3: начало - 16, конец - 20, а середина - 18. nums [mid] равно 19, что равно ‹target (20), поэтому start станет mid + 1, то есть 19.
Сравнение 4: начало - 19, конец - 20, а середина - 19. nums [mid] равно 20, что равно target (20), поэтому мы получили результат.
Как видите, мы получили результат только в 4-х сравнениях. Это сила двоичного поиска, и мы всегда должны пытаться использовать ее, если у нас есть отсортированный массив.
Теперь переходим к нашей основной задаче поиска первой и последней позиции. Ниже приведен код Java для решения этой проблемы с помощью двоичного поиска.
package com.ds.arrays; public class FirstAndLastPosition { public static int[] searchRange(int[] nums, int target) { int[] result = new int[2]; result[0] = -1; result[1] = -1; int start = 0; int end = nums.length - 1; while (start <= end) { int mid = start + ((end - start) / 2); if (nums[mid] == target) { result[0] = findStart(nums, start, mid, target); result[1] = findEnd(nums, mid, end, target); return result; } else if (nums[mid] < target) { start = mid + 1; } else { end = mid - 1; } } return result; } public static int findStart(int[] nums, int start, int end, int target) { int result = end; while (start <= end) { int mid = start + ((end - start) / 2); if (nums[mid] == target) { result = mid; end = mid - 1; } else { start = mid + 1; } } return result; } public static int findEnd(int[] nums, int start, int end, int target) { int result = start; while (start <= end) { int mid = start + ((end - start) / 2); if (nums[mid] == target) { result = mid; start = mid + 1; } else { end = mid - 1; } } return result; } }