[PYTHON] Algorithmus Gymnastik 20 Duplikate entfernen

Remove Duplicates

Ein Array sortierter Zahlen wird als Argument übergeben, um alle Duplikate daraus zu entfernen. Keine neue Datenstruktur verwendet Gibt die neue Länge des Arrays zurück, nachdem die vorhandenen Duplikate entfernt wurden.

Beispiel

Input: [2, 3, 3, 3, 6, 9, 9] Output: 4 ([2, 3, 6, 9])

Input: [2, 2, 2, 11] Output: 2 ([2, 11])

Solution

# The time complexity: O(N)
# Space Complexity: O(1)

def remove_duplicates(arr):
  # index of the next non-duplicate element
  next_non_duplicate = 1

  i = 1
  while(i < len(arr)):
    if arr[next_non_duplicate - 1] != arr[i]:
      arr[next_non_duplicate] = arr[i]
      next_non_duplicate += 1
    i += 1

  return next_non_duplicate

Ähnlich

Gibt ein unsortiertes Array von Zahlen und den Zielschlüssel an, entfernt alle Elemente, die mit dem Schlüssel übereinstimmen, und gibt die neue Länge des Arrays zurück.

Beispiel

Input: [3, 2, 3, 6, 3, 10, 9, 3], Key=3 Output: 4 ([2, 6, 10, 9])

Input: [2, 11, 2, 2, 1], Key=2 Output: 2 ([11, 1])

Implementierung

# The time complexity: O(N)
# Space Complexity: O(1)

def remove_element(arr, key):
  nextElement = 0  # index of the next element which is not 'key'
  for i in range(len(arr)):
    if arr[i] != key:
      arr[nextElement] = arr[i]
      nextElement += 1

  return nextElement