Swift | LeetCode

Задача: 34. Find First and Last Position of Element in Sorted Array
Сложность: medium

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

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

Вы должны написать алгоритм со временной сложностью O(log n).

Пример:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

👨‍💻

Алгоритм:

1⃣Определите функцию под названием findBound, которая принимает три аргумента: массив, целевое значение для поиска и булевое значение isFirst, указывающее, ищем ли мы первое или последнее вхождение цели.
Мы используем 2 переменные для отслеживания подмассива, который мы сканируем. Назовем их begin и end. Изначально begin устанавливается в 0, а end — в последний индекс массива.

2⃣Мы итерируем, пока begin не станет больше, чем end.
На каждом шаге мы вычисляем средний элемент mid = (begin + end) / 2. Мы используем значение среднего элемента, чтобы решить, какую половину массива нам нужно искать.
Если nums[mid] == target:
Если isFirst true — это означает, что мы пытаемся найти первое вхождение элемента. Если mid == begin или nums[mid - 1] != target, тогда мы возвращаем mid как первое вхождение цели. В противном случае мы обновляем end = mid - 1.
Если isFirst false — это означает, что мы пытаемся найти последнее вхождение элемента. Если mid == end или nums[mid + 1] != target, тогда мы возвращаем mid как последнее вхождение цели. В противном случае мы обновляем begin = mid + 1.

3⃣Если nums[mid] > target — мы обновляем end = mid - 1, так как мы должны отбросить правую сторону массива, поскольку средний элемент больше цели.
Если nums[mid] < target — мы обновляем begin = mid + 1, так как мы должны отбросить левую сторону массива, поскольку средний элемент меньше цели.
В конце нашей функции мы возвращаем значение -1, что указывает на то, что цель не найдена в массиве.
В основной функции searchRange мы сначала вызываем findBound с isFirst, установленным в true. Если это значение равно -1, мы можем просто вернуть [-1, -1]. В противном случае мы вызываем findBound с isFirst, установленным в false, чтобы получить последнее вхождение, а затем возвращаем результат.

😎

Решение:

func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
    let firstOccurrence = findBound(nums, target, true)
    if firstOccurrence == -1 {
        return [-1, -1]
    }
    let lastOccurrence = findBound(nums, target, false)
    return [firstOccurrence, lastOccurrence]
}

func findBound(_ nums: [Int], _ target: Int, _ isFirst: Bool) -> Int {
    let N = nums.count
    var begin = 0
    var end = N - 1
    while begin <= end {
        let mid = (begin + end) / 2
        if nums[mid] == target {
            if isFirst {
                if mid == begin || nums[mid - 1] != target {
                    return mid
                }
                end = mid - 1
            } else {
                if mid == end || nums[mid + 1] != target {
                    return mid
                }
                begin = mid + 1
            }
        } else if nums[mid] > target {
            end = mid - 1
        } else {
            begin = mid + 1
        }
    }
    return -1
}

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post