Dividir Array en Arrays con Diferencia Máxima
Se te da un array de enteros nums de tamaño n donde n es múltiplo de 3 y un entero positivo k.
Divide el array nums en n / 3 arrays de tamaño 3 que satisfagan la siguiente condición:
- La diferencia entre dos elementos cualquiera en un array es menor o igual a
k.
Devuelve un array 2D que contenga los arrays. Si es imposible satisfacer las condiciones, Devuelve un array vacío. Y si hay múltiples respuestas, Devuelve cualquiera de ellas.
Ejemplos
Ejemplo 1:
Input: nums = [1,3,4,8,7,9,3,5,1], k = 2 Output: [[1,1,3],[3,4,5],[7,8,9]] Explicación: La diferencia entre cualquier dos elementos en cada array es menor o igual a 2.
Ejemplo 2:
Input: nums = [2,4,2,2,5,2], k = 2 Output: [] Explicación: Las diferentes formas de dividir nums en 2 arrays de tamaño 3 son: [[2,2,2],[2,4,5]] (y sus permutaciones) [[2,2,4],[2,2,5]] (y sus permutaciones) Porque hay cuatro 2s habrá un array con los elementos 2 y 5 sin importar cómo lo dividamos. Como 5 - 2 = 3 > k, la condición no se satisface y por lo tanto no hay una división válida.
Ejemplo 3:
Input: nums = [4,2,9,8,2,12,7,12,10,5,8,5,5,7,9,2,5,11], k = 14 Output: [[2,2,12],[4,8,5],[5,9,7],[7,8,5],[5,9,10],[11,12,2]] Explicación: La diferencia entre cualquier dos elementos en cada array es menor o igual a 14.
Soluciones
Python
class Solution:
def divideArray(self, nums: List[int], k: int) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
for i in range(2, n, 3):
if nums[i] - nums[i - 2] > k:
return []
res.append([nums[i - 2], nums[i - 1], nums[i]])
return res