Gymnastique d'algorithme 20 Supprimer les doublons

Remove Duplicates

Un tableau de nombres triés est passé comme argument pour en supprimer tous les doublons. Aucune nouvelle structure de données utilisée Après avoir supprimé les doublons sur place, il renvoie la nouvelle longueur du tableau.

Exemple

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

Similaire

Spécifie un tableau non trié de nombres et la "clé" cible, supprime tous les éléments qui correspondent à la "clé" et renvoie la nouvelle longueur du tableau.

Exemple

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])

la mise en oeuvre

# 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