[PYTHON] Gymnastique algorithmique 22 Mise au carré d'un tableau trié

Squaring a Sorted Array

Prend le tableau trié comme argument et renvoie un nouveau tableau contenant les carrés de tous les nombres du tableau dans l'ordre croissant.

Input: [-2, -1, 0, 2, 3] Output: [0, 1, 4, 4, 9]

Input: [-3, -1, 0, 1, 2] Output: [0 1 1 4 9]

Solution Puisque le tableau passé en argument est trié, vous pouvez obtenir les nombres maximum et minimum aux deux extrémités, vous pouvez donc utiliser deux pointeurs commençant aux deux extrémités du tableau. Après cela, comparez les valeurs au carré et ajoutez la valeur la plus élevée à partir de l'extrémité droite.

la mise en oeuvre

def make_squares(arr):
  # Time Complexity -> O(n)
  # Space Complexity -> O(n)
  squares = [0 for _ in range(len(arr))]
  left_pointer, right_pointer = 0, len(arr) - 1
  highestValIndex = len(arr) -1
  while left_pointer <= right_pointer:
    left_val = arr[left_pointer]**2
    right_val = arr[right_pointer]**2
    if left_val <= right_val:
      squares[highestValIndex] = right_val
      right_pointer -= 1
    else:
      squares[highestValIndex] = left_val
      left_pointer += 1
    highestValIndex -= 1
  return squares