Minimizar la Diferencia Máxima de Pares
Se te da un arreglo de enteros nums indexado desde 0 y un entero p. Encuentra p pares de índices de nums tal que la diferencia máxima entre todos los pares sea minimizada. Además, asegúrate de que ningún índice aparezca más de una vez entre los p pares.
Ten en cuenta que para un par de elementos en los índices i y j, la diferencia de este par es |nums[i] - nums[j]|, donde |x| representa el valor absoluto de x.
Devuelve la diferencia máxima mínima entre todos los p pares. Definimos el máximo de un conjunto vacío como cero.
Ejemplos
Ejemplo 1:
Input: nums = [10,1,2,7,1,3], p = 2 Output: 1 Explicación: El primer par se forma con los índices 1 y 4, y el segundo par se forma con los índices 2 y 5. La diferencia máxima es max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1. Por lo tanto, devolvemos 1.
Ejemplo 2:
Input: nums = [4,2,1,2], p = 1 Output: 0 Explicación: Dejemos que los índices 1 y 3 formen un par. La diferencia de ese par es |2 - 2| = 0, que es el mínimo que podemos obtener.
Soluciones
Python
lass Solution:
def isPossible(self, nums, val, p):
count = 0
i = 1
while i < len(nums):
if nums[i] - nums[i - 1] <= val:
count += 1
i += 2
else:
i += 1
return count >= p
def minimizeMax(self, nums, p):
nums.sort()
low, high = 0, nums[-1]
ans = float('inf')
while low <= high:
mid = low + (high - low) // 2
if self.isPossible(nums, mid, p):
ans = mid
high = mid - 1
else:
low = mid + 1
return ans