Ich habe jeden Tag LeetCode ausprobiert 26. Duplikate aus sortiertem Array entfernen (Python, Go)

Einführung

@Ishishow betreibt eine kostenlose englische Word-Site E-tan.

Ich möchte jeden Tag an Letcode arbeiten, um meine Fähigkeiten als Programmierer zu verbessern und meine eigene Art der Lösung zu finden.

Was ist Leetcode?

leetcode.com Dies ist die Praxis des Codierens von Interviews für Softwareentwickler. Insgesamt wurden mehr als 1.500 Codierungsfragen gestellt, und es scheint, dass in tatsächlichen Interviews häufig dieselben Fragen gestellt werden.

Einführung in den Golang + Algorithmus Ich werde ihn mit go und Python lösen, um das Gehirn zu stärken. (Python ist schwach, aber erfahren)

8. Frage (Problem 26)

26. Remove Duplicates from Sorted Array

--Probleminhalt (japanische Übersetzung)

Geben Sie das sortierte Array * nums * an und duplizieren Sie [** an Ort und Stelle **](https: // en. Löschen Sie es unter wikipedia.org/wiki/In-place_algorithm).

Weisen Sie keinem anderen Array zusätzlichen Speicherplatz zu. O (1) muss ** und ** modifiziert ** im Eingabearray [an Ort und Stelle] verwendet werden (https://en.wikipedia.org/wiki/In-place_algorithm) ** ..

** Klarstellung: **

Sie wissen nicht, warum die Antwort ein Array ist, wenn der Rückgabewert eine Ganzzahl ist?

Beachten Sie, dass das Eingabearray als ** Referenz ** übergeben wird. Dies bedeutet, dass Änderungen am Eingabearray auch für den Anrufer sichtbar sind.

Intern können Sie darüber nachdenken.

//nums werden als Referenz übergeben. (Das heißt, ohne eine Kopie zu machen)
int len = removeDuplicates（nums）;

//Änderungen an Nummern in der Funktion sind dem Anrufer bekannt.
//Druckt das erste len-Element mit der von der Funktion zurückgegebenen Länge.
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.

Tipp 1

Ein wichtiger Punkt, auf den Sie sich in dieser Ausgabe konzentrieren sollten, ist das sortierte Eingabearray. Welche Positionen haben überlappende Elemente im Array, wenn ein bestimmtes Array sortiert wird? Siehe das Bild oben für die Antwort. Wenn Sie die Position eines der Elemente kennen, kennen Sie die Position aller überlappenden Elemente?

Tipp 2

Das Array muss an Ort und Stelle geändert werden, und die endgültige Arraygröße kann kleiner als die Größe des Eingabearrays sein. Daher müssen wir hier den Zwei-Zeiger-Ansatz verwenden. Einer verfolgt die aktuellen Elemente des ursprünglichen Arrays und der andere verfolgt nur eindeutige Elemente.

Tipp 3

Sobald ein Element gefunden wurde, müssen Sie seine Duplizierung ** umgehen ** und mit dem nächsten eindeutigen Element fortfahren.

Denkweise

1. Erstellen Sie einen neuen Index (nw_index)

2. Drehen Sie die Schleife len (nums) mal und fahren Sie so fort, wie sie ist, wenn sie sich überlappt

3. Wenn keine Duplikate vorhanden sind, ersetzen Sie die neue Indexnummer durch diesen Wert.

4. Der Rückgabewert gibt die Länge zurück, also addieren Sie 1

--Antwortcode

  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)

• Ich werde es auch in Go schreiben!

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

Eine andere Lösung

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

Verfahrenserklärung

Mit set () in Set-Typ (Aggregattyp) konvertieren

Was ist ein Set-Typ?

Der Typ "set" ist eine Sammlung nicht überlappender Elemente (Elemente, die nicht denselben Wert haben, eindeutige Elemente) und kann Mengenoperationen wie Summenmenge, Produktmenge und Differenzmenge ausführen.

Da set ein Set ist, wird die Reihenfolge durcheinander gebracht. Verwenden Sie daher die sortierte Funktion, um sie in aufsteigender Reihenfolge zurückzugeben.

Weisen Sie nums [:] einen Verweis zu. Der Grund, warum nums = hier nicht gesetzt ist, ist, dass ein neues Objekt erstellt wird und kein Speicher belegt wird.