J'ai essayé LeetCode tous les jours 26. Supprimer les doublons du tableau trié (Python, Go)

introduction

@Ishishow gère un site de mots anglais gratuit E-tan.

J'aimerais travailler quotidiennement sur letcode pour améliorer mes capacités de programmeur et donner ma propre façon de le résoudre.

Qu'est-ce que Leetcode

leetcode.com C'est la pratique de coder des interviews pour les développeurs de logiciels. Au total, plus de 1 500 questions de codage ont été affichées, et il semble que les mêmes questions soient souvent posées lors d'entretiens réels.

Introduction à l'algorithme golang + Je vais le résoudre avec go et Python pour renforcer le cerveau. (Python est faible mais expérimenté)

8e question (problème 26)

Remove Duplicates from Sorted Array

Contenu du problème (traduction japonaise)

Spécifiez le tableau trié * nums , et dupliquez [* en place **](https: // en.) Pour que chaque élément ne s'affiche que 1 * fois * et renvoie une nouvelle longueur. Supprimez-le sur wikipedia.org/wiki/In-place_algorithm).

N'allouez pas d'espace supplémentaire pour une autre baie. O (1) doit être utilisé ** et ** modifié ** dans le tableau d'entrée in-place ** ..

** Précision: **

Vous ne savez pas pourquoi la réponse est un tableau alors que la valeur de retour est un entier?

Notez que le tableau d'entrée est passé par ** reference **. Cela signifie que les modifications apportées au tableau d'entrée seront également visibles par l'appelant.

En interne, vous pouvez y penser.
//nums sont passés par référence. (Autrement dit, sans faire de copie)
int len = removeDuplicates（nums）;

//Les modifications apportées aux nombres dans la fonction sont connues de l'appelant.
//Imprime le premier élément len en utilisant la longueur renvoyée par la fonction.
for（int i = 0; i <len; i ++）{
    print（nums [i]）;
}

Example 1:

  Input: nums = [1,1,2]
  Output: 2, nums = [1,2]
  Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

  Input: nums = [0,0,1,1,1,2,2,3,3,4]
  Output: 5, nums = [0,1,2,3,4]
  Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Astuce 1

Un point important sur lequel se concentrer dans ce problème est le tableau d'entrée trié. En ce qui concerne les éléments qui se chevauchent, quelles sont leurs positions dans le tableau lorsqu'un tableau particulier est trié? Voir l'image ci-dessus pour la réponse. Si vous connaissez la position de l'un des éléments, connaissez-vous la position de tous les éléments qui se chevauchent?

Astuce 2

Le tableau doit être modifié sur place et la taille finale du tableau peut être inférieure à la taille du tableau d'entrée. Par conséquent, nous devons utiliser ici l'approche à deux points. L'un garde la trace des éléments actuels du tableau d'origine, et l'autre ne garde la trace que des éléments uniques.

Astuce 3

Fondamentalement, une fois qu'un élément est trouvé, vous devez ** contourner ** sa duplication et passer à l'élément unique suivant.

Façon de penser

Créez un nouvel index (nw_index)
Tournez la boucle len (nums) fois et procédez comme elle est si elle se chevauche
S'il n'y a pas de doublons, remplacez cette valeur par le nouveau numéro d'index.
La valeur de retour renvoie la longueur, donc ajoutez 1

--Code de réponse

  class Solution(object):
      def removeDuplicates(self, nums):
          nw_index = 0
          for i in range(len(nums)):
              if nums[nw_index] != nums[i]:
                  nw_index +=1
                  nums[nw_index] = nums[i]
          return (nw_index + 1)

Je l'écrirai aussi en Go!

func removeDuplicates(nums []int) int {
	nw_index := 0
	for _, num := range nums {
		if nums[nw_index] != num {
			nw_index++
			nums[nw_index] = num
		}
	}

	return (nw_index + 1)
}

Une autre solution

def removeDuplicates(self, nums):
    nums[:] = sorted(set(nums))
    return len(nums)

Explication de la procédure

Convertir en type d'ensemble (type d'agrégat) avec set ()

Qu'est-ce qu'un type d'ensemble?

Le type set est une collection d'éléments qui ne se chevauchent pas (éléments qui n'ont pas la même valeur, éléments uniques), et peut effectuer des opérations d'ensemble telles que l'ensemble de somme, l'ensemble de produits et l'ensemble de différences.

Puisque l'ensemble est un ensemble, l'ordre sera faussé, utilisez donc la fonction triée pour le renvoyer dans l'ordre croissant.

Attribuez une référence à nums [:]. La raison pour laquelle nums = n'est pas défini ici est qu'un nouvel objet est créé et que la mémoire n'est pas consommée.