Рубрики
Без рубрики

Решение: найдите первую и последнюю позицию элемента в отсортированном массиве

Это является частью серии пояснений решения LeetCode (индекс). Если вам понравилось это решение или … помеченные алгоритмами, JavaScript, Java, Python.

Решения LeetCode (161 часть серии)

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашел его полезным, Пожалуйста, как этот пост и/или УПОТАТЬ Мое решение пост на форумах LeetCode Отказ

Проблема лецкода № 34 (средний): найдите первую и последнюю позицию элемента в отсортированном массиве

Описание:

( Перейти к : Идея решения Код : JavaScript | Python |. Java |. C ++

Учитывая массив целых чисел Nums Сортировано в порядке возрастания, найдите начальную и окончание положения данного цель ценность.

Если цель не найден в массиве, возврат [-1, -1] .

Продолжайте : Не могли бы вы написать алгоритм с O (log n) Сложность времени выполнения?

Примеры:

Вход: nums = [ 5,7,7,8,8,10],
Вывод: [3,4]
Вход: nums = [ 5,7,7,8,8,10],
Вывод: [-1,-1]
Вход: nums = [],
Вывод: [-1,-1]

Ограничения:

  • 0.Length ^ 5.
  • -10 ^ 9 [I] ^ 9
  • Nums это не уменьшающийся массив.
  • -10^9^9

Идея:

( Перейти к : Описание проблемы Код : JavaScript | Python |. Java |. C ++

Эта проблема очень почти определение Бинарный поиск Отказ Двоичный поиск позволяет нам найти индекс вставки для целевого номера в отсортированном массиве. Это называется поиском «двоичного», потому что на каждом шагу он половиняет входную массив и определяет, в какую половину принадлежат номер. Поскольку двоичный поиск способен устранить половину оставшегося массива в каждой итерации, он может выполнить свою цель с Сложность времени O (log n) Отказ

В этом случае, однако, мы не просто хотим выяснить, где целевой номер ( T ) будет размещен в массиве Nums ( n ), мы хотим дополнительно узнать, если T на самом деле существует в N , а также начальные и конечные индексы.

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

Во-первых, мы можем выполнить стандартный левый двоичный поиск ( Найти ) на T Отказ Далее мы можем легко проверить, чтобы увидеть Если T существует в N Уже путем проверки значения, хранящегося в результате этого первого поиска ( n [TLEFT] ). Если мы не найдем T При этом индекс, то T не существует в N И мы должны Вернуться [-1, -1] Отказ

В противном случае нам все еще нужно найти правильный конец диапазона T Значения в N Отказ Для этого мы можем просто использовать найти Опять же, на этот раз со следующим целым числом ( T + 1 ). Так как это найдет индекс после конец диапазона T Значения, мы можем просто перейти назад на одну позицию, чтобы найти конец T диапазон.

Теперь, когда у нас есть наш ассортимент, мы можем вернуть Это.

  • Сложность времени: O (log n) Для двоичного поиска
  • Космическая сложность: O (1)

Выполнение:

Python имеет встроенные двоичные поисковые функции для обеих сторон: bisect_left () и bisect_right () Отказ

Встроенная функция для Java, Массивы. BinarySearch () Не находит левую точку вставки, поэтому легче определить нашу собственную бинарную функцию поиска.

C ++ можно использовать встроенный функцию eval_range () , который возвращает указатели итератора на диапазон значений T.

Код JavaScript:

( Перейти к : Описание проблемы Идея решения

var searchRange = function(N, T) {
    const find = (target, arr, left=0, right=arr.length) => {
        while (left <= right) {
            let mid = left + right >> 1
            if (arr[mid] < target) left = mid + 1
            else right = mid - 1
        }
        return left
    } 
    let Tleft = find(T, N)
    if (N[Tleft] !== T) return [-1,-1]
    return [Tleft, find(T+1, N, Tleft) - 1]
};

Код Python:

( Перейти к : Описание проблемы Идея решения

w/bisect_left () & bisect_right ():
class Solution:
    def searchRange(self, N: List[int], T: int) -> List[int]:
        Tleft = bisect_left(N, T)
        if Tleft == len(N) or N[Tleft] != T: return [-1, -1]
        return [Tleft, bisect_right(N, T) - 1]
ж/на заказ бинарный поиск:
class Solution:
    def searchRange(self, N: List[int], T: int) -> List[int]:
        def find(target, arr, left=0):
            right = len(arr) - 1
            while left <= right:
                mid = left + right >> 1
                if arr[mid] < target: left = mid + 1
                else: right = mid - 1
            return left
        Tleft = find(T, N)
        if Tleft == len(N) or N[Tleft] != T: return [-1, -1]
        return [Tleft, find(T+1, N, Tleft) - 1]

Java код:

( Перейти к : Описание проблемы Идея решения

class Solution {
    public int[] searchRange(int[] N, int T) {
        int Tleft = find(T, N, 0);
        if (Tleft == N.length || N[Tleft] != T) return new int[] {-1, -1};
        return new int[] {Tleft, find(T+1, N, Tleft) - 1};
    }
    public int find(int target, int[] arr, int left) {
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + right >> 1;
            if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
}

C ++ код:

( Перейти к : Описание проблемы Идея решения

w/eval_range ():
class Solution {
public:
    vector searchRange(vector& N, int T) {
        pair::iterator,vector::iterator> range;
        range = equal_range(N.begin(), N.end(), T);
        int Tleft = distance(N.begin(), range.first);
        if (Tleft == N.size() || N[Tleft] != T) return {-1, -1};
        return {Tleft, (int)distance(N.begin(), range.second) - 1};
    }
};
ж/на заказ бинарный поиск:
class Solution {
public:
    vector searchRange(vector& N, int T) {
        int Tleft = find(T, N);
        if (Tleft == N.size() || N[Tleft] != T) return {-1, -1};
        return {Tleft, find(T+1, N, Tleft) - 1};
    }
    int find(int target, vector arr, int left=0) {
        int right = arr.size() - 1;
        while (left <= right) {
            int mid = left + right >> 1;
            if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
};

Решения LeetCode (161 часть серии)

Оригинал: “https://dev.to/seanpgallivan/solution-find-first-and-last-position-of-element-in-sorted-array-2fg0”

Читайте ещё по теме: