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

Постановка проблемы:-

Предположим, что массив длины n, отсортированный в порядке возрастания, вращается между 1 и n разами. Например, массив nums = [0,1,2,4,5,6,7] может стать следующим:

  • [4,5,6,7,0,1,2], если он был повернут 4 раз.
  • [0,1,2,4,5,6,7], если он был повернут 7 раз.

Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Учитывая отсортированный повернутый массив nums из уникальных элементов, вернуть минимальный элемент этого массива.

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

Совет. Поскольку вам предлагается написать алгоритм, который работает за 0(log n) раз, это означает, что вам нужно выполнить двоичный поиск.

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """  
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        return nums[left]
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Пояснение:-

Этот алгоритм имеет временную сложность O(log n) и пространственную сложность O(1). В этом алгоритме он находит точку поворота (индекс, с которого массив начинает вращаться), сравнивая средний элемент с крайним правым элементом. Если средний элемент больше, чем самый правый элемент, точка поворота находится справа от среднего элемента. Если средний элемент меньше или равен крайнему правому элементу, точка поворота находится слева от среднего элемента. Он продолжает сокращать пространство поиска, проверяя эти условия, пока левый указатель не сравняется с правым указателем, который является точкой поворота.

Проверьте мой репозиторий Github, чтобы решить больше вопросов по кодированию: -



GitHub — klaus19/LeetcodeinPython: проблемы с leetcode в python
Вы не можете выполнить это действие в данный момент. Вы вошли в другую вкладку или окно. Вы вышли на другой вкладке или…github.com



Следите за моими другими вопросами из этой серии здесь: -



Решение проблем Neetcode 150 (Сегодняшняя проблема: - Подмассив максимального продукта)
Это задача среднего уровня Leetcode, которую обычно задают в технологических компаниях, где вам нужно найти максимальный продукт…medium.com





Решение проблем Neetcode 150 (Сегодняшняя проблема: Продукт массива, кроме себя)
Сегодня мы собираемся решить один из наиболее часто задаваемых вопросов на собеседованиях по программированию в компаниях MAANG. , это…medium.com



Удачного кодирования :)