[LeetCode] 0153. encontrar el mínimo en una matriz ordenada rotada

encontrar el mínimo en una matriz ordenada rotada

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

Tabla de contenido

Medio


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 girado 4 veces.
  • [0,1,2,4,5,6,7] si estuviera girado 7 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 entre 1 y norte 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))
				
			
es_ESEspañol