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

Recommended Posts

Gymnastique d'algorithme 20 Supprimer les doublons
Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Gymnastique algorithmique 24 Inverser une liste liée
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée