[PYTHON] Algorithmusgymnastik 22 Quadrieren eines sortierten Arrays

Squaring a Sorted Array

Nimmt das sortierte Array als Argument und gibt ein neues Array zurück, das die Quadrate aller Zahlen im Array in aufsteigender Reihenfolge enthält.

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 Da das als Argument übergebene Array sortiert ist, können Sie die maximale und minimale Anzahl an beiden Enden abrufen, sodass Sie zwei Zeiger verwenden können, die an beiden Enden des Arrays beginnen. Vergleichen Sie danach die quadratischen Werte und fügen Sie den größeren Wert am rechten Ende hinzu.

Implementierung

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