Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github
Supongamos una matriz de longitud norte
ordenado en orden ascendente es girado entre 1
y norte
veces. números = [0,1,2,4,5,6,7]
podría convertirse en:
[4,5,6,7,0,1,2]
si estuviera girado4
veces.[0,1,2,4,5,6,7]
si estuviera girado7
veces.
Note que giratorio una matriz [un[0], un[1], un[2], ..., un[n-1]]
1 vez da como resultado la matriz [un[n-1], un[0], un[1], un[2], ..., un[n-2]]
.
Dada la matriz rotada ordenada números
de único elementos, retorno el elemento mínimo de esta matriz.
Debes escribir un algoritmo que se ejecute en O(log n) tiempo.
Ejemplo 1:
Aporte: números = [3,4,5,1,2] Producción: 1 Explicación: La matriz original fue [1,2,3,4,5] rotada 3 veces.
Ejemplo 2:
Aporte: números = [4,5,6,7,0,1,2] Producción: 0 Explicación: La matriz original era [0,1,2,4,5,6,7] y se giró 4 veces.
Ejemplo 3:
Aporte: números = [11,13,15,17] Producción: 11 Explicación: La matriz original era [11,13,15,17] y se giró 4 veces.
Restricciones:
n == números.longitud
1 <= norte <= 5000
-5000 <= números[i] <= 5000
- Todos los números enteros de
números
son único. números
se clasifica y rota entre1
ynorte
veces.
Pitón
Complejidad de tiempo de #: O(logn) Complejidad de espacio de #: O(1) al escribir import List class Solución: def findMin(self, nums: List[int]) -> int: if len(nums) == 1: devolver nums [0] izquierda, derecha = 0, len(nums) - 1 if nums[derecha] > nums[0]: devuelve nums[0] mientras izquierda <= derecha: mid = izquierda + (derecha - izquierda) // 2 si nums[mid] > nums[mid + 1]: devuelve nums[mid+1] si nums[mid] < nums[mid - 1]: devuelve nums[mid] si nums[mid] > nums[-1]: izquierda = mid + 1 else: right = mid - 1 return nums[mid] nums = [11, 13, 15, 17] print(Solution().findMin(nums))