Array-Grundlagen und In-Place-Operationen
Wiederholen Sie Indizierung und Mutation und lernen Sie die häufigsten Array-Fallen in Interviews kennen, etwa Off-by-one-Fehler und das Ändern einer Liste während der Iteration.
Array-Grundlagen und In-Place-Operationen ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Arrays als zusammenhängender Speicher
Unter der Haube wird eine Python-Liste von einem dynamischen Array unterstützt — einem zusammenhängenden Speicherblock, in dem Elemente an aufeinanderfolgenden Adressen gespeichert sind. Dieses Layout ermöglicht einen O(1)-Zufriff per Index: Python berechnet address = base + index × element_size sofort. Einfügen oder Löschen in der Mitte erfordert, alle nachfolgenden Elemente zu verschieben, was O(n) kostet. Diese Asymmetrie ist der Grund für die meisten Diskussionen über Array-Abwägungen in Interviews.
nums = [10, 20, 30, 40, 50]
# O(1) random access
print(nums[2]) # 30
print(nums[-1]) # 50
# O(1) append (amortised)
nums.append(60)
print(nums) # [10,20,30,40,50,60]
# O(n) insert at beginning
nums.insert(0, 0) # shifts all elements right
print(nums) # [0,10,20,30,40,50,60]Off-by-One: Der klassische Array-Fehler
Off-by-one-Fehler sind die häufigste Ursache für falsche Antworten bei Array-Problemen. Die 0-basierte Indizierung von Python bedeutet, dass der letzte gültige Index len(arr) - 1 ist. Entscheiden Sie beim Schreiben von Schleifen anhand der Randbedingung, ob Sie < oder <= benötigen, und prüfen Sie dabei die kleinste gültige Eingabe (n=1 oder n=2). Verfolgen Sie Ihre Randbedingung vor dem Absenden immer anhand konkreter Beispiele.
def find_max(nums):
# Use len(nums)-1 as last index
max_val = nums[0] # safe if n >= 1
for i in range(1, len(nums)): # start at 1, not 0
if nums[i] > max_val:
max_val = nums[i]
return max_val
print(find_max([3, 1, 4, 1, 5])) # 5
print(find_max([7])) # 7 (single element)
# Would crash if we accessed nums[len(nums)]In-Place-Umkehrung mit zwei Zeigern
Beim Umkehren eines Arrays in-place beginnen zwei Zeiger an den entgegengesetzten Enden und tauschen sich nach innen vor, bis sie sich treffen. Das benötigt O(1) zusätzlichen Speicher und O(n) Zeit. Die Bedingung left < right (streng kleiner) stellt die Korrektheit für gerade und ungerade Längen sicher — bei einer ungeraden Anzahl von Elementen bleibt das mittlere Element automatisch an seiner Position.
def reverse_inplace(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
# Space: O(1) Time: O(n)
a = [1, 2, 3, 4, 5]
reverse_inplace(a)
print(a) # [5, 4, 3, 2, 1]
b = [1, 2, 3]
reverse_inplace(b)
print(b) # [3, 2, 1] middle element unchangedEin Array In-Place rotieren
Ein Array lässt sich um k Positionen nach rechts rotieren, indem Sie es In-Place in drei Abschnitten umkehren: zuerst das gesamte Array, dann die ersten k Elemente und anschließend die übrigen n-k Elemente. Das erreicht O(n) Zeit und O(1) Speicher — deutlich besser als der Ansatz mit O(n) Speicher, bei dem Slicing und Verkettung verwendet werden. Reduzieren Sie k immer modulo n, um k ≥ n zu berücksichtigen.
def rotate(nums, k):
n = len(nums)
k %= n # handle k >= n
def rev(l, r):
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1; r -= 1
rev(0, n-1) # reverse all
rev(0, k-1) # reverse first k
rev(k, n-1) # reverse rest
a = [1, 2, 3, 4, 5, 6, 7]
rotate(a, 3)
print(a) # [5, 6, 7, 1, 2, 3, 4]Elemente In-Place entfernen
Beim in-place-Entfernen von Duplikaten oder Zielwerten verfolgt ein Schreibzeiger, an welche Position das nächste gültige Element geschrieben werden soll. Der Lesezeiger durchläuft das Array vorwärts; findet er ein gültiges Element, kopiert er es an die Schreibposition und bewegt beide Zeiger weiter. Das ist das grundlegende Muster für LeetCode-Probleme wie 'remove element', 'remove duplicates from sorted array' und 'move zeroes'.
def remove_element(nums, val):
write = 0
for read in range(len(nums)):
if nums[read] != val:
nums[write] = nums[read]
write += 1
return write # new length
nums = [3, 2, 2, 3]
new_len = remove_element(nums, 3)
print(nums[:new_len]) # [2, 2]
nums2 = [0, 1, 2, 2, 3, 0, 4, 2]
new_len2 = remove_element(nums2, 2)
print(nums2[:new_len2]) # [0, 1, 3, 0, 4]Nullen verschieben: Lese-Schreib-Zeiger
Verschieben Sie alle Nullen ans Ende eines Arrays und bewahren Sie dabei die Reihenfolge der Nichtnull-Elemente. Der Ansatz mit einem Lese-Schreib-Zeiger platziert jedes Nichtnull-Element an der Schreibposition und füllt anschließend den hinteren Bereich mit Nullen auf. Ein alternativer Ansatz verschiebt Nullen durch Vertauschen nach hinten und bewahrt dabei die Reihenfolge, ohne einen zweiten Auffüll-Durchlauf. Beide benötigen O(n) Zeit und O(1) Speicherplatz.
def move_zeroes(nums):
write = 0
# Move all non-zeroes to front
for read in range(len(nums)):
if nums[read] != 0:
nums[write] = nums[read]
write += 1
# Fill rest with zeroes
while write < len(nums):
nums[write] = 0
write += 1
a = [0, 1, 0, 3, 12]
move_zeroes(a)
print(a) # [1, 3, 12, 0, 0]Quadrieren und In-Place-Sortieren
Bei einem sortierten Array von Ganzzahlen, das möglicherweise negative Werte enthält, sollen Sie ein Array mit deren Quadraten in sortierter Reihenfolge zurückgeben. Der naive Ansatz quadriert die Werte und sortiert sie anschließend: O(n log n). Der optimale Zwei-Zeiger-Ansatz nutzt die Tatsache, dass die größten Quadrate von einem der beiden Enden des sortierten Eingabearrays stammen: Vergleichen Sie die Absolutwerte des Elements ganz links und des Elements ganz rechts und füllen Sie das Ergebnis in O(n) Zeit von rechts nach links.
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1 # fill from the right
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]Pivot finden und partitionieren
Das Problem der niederländischen Nationalflagge teilt ein Array mithilfe von drei Zeigern in-place in drei Bereiche auf (kleiner als, gleich dem bzw. größer als das Pivot-Element). Dies ist der zentrale Teilschritt von Quicksort und die Lösung für LeetCode 'sort colors'. Die Aufrechterhaltung der Invariante, dass Elemente vor dem low-Zeiger < pivot und Elemente nach dem high-Zeiger > pivot sind, treibt den Algorithmus voran.
def sort_colors(nums):
# Dutch national flag: 0s, 1s, 2s
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1; mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1 # don't advance mid: new nums[mid] unexamined
a = [2, 0, 2, 1, 1, 0]
sort_colors(a)
print(a) # [0, 0, 1, 1, 2, 2]Array-Elemente während der Iteration ändern
Sie können Elementwerte sicher ändern (z. B. mit -1 multiplizieren, um besuchte Elemente zu markieren), dürfen aber niemals die Länge einer Liste innerhalb einer for-Schleife ändern. Ein sicherer Kodierungstrick besteht darin, vorübergehend zwei Werte in einer einzigen Ganzzahl zu kodieren (z. B. über das Vorzeichenbit), um pro Element ein zusätzliches boolesches Merkmal zu simulieren, ohne zusätzlichen Speicher zu reservieren. Dies kommt in Aufgaben wie 'find all numbers that disappeared in an array.' zum Einsatz.
def find_disappeared(nums):
# Mark visited by negating the value at the index
for n in nums:
idx = abs(n) - 1
if nums[idx] > 0:
nums[idx] *= -1 # mark as seen
# Indices with positive values are missing
return [i + 1 for i, v in enumerate(nums) if v > 0]
print(find_disappeared([4, 3, 2, 7, 8, 2, 3, 1]))
# [5, 6] -- O(n) time, O(1) extra spaceCheckliste für Array-Muster bei Interviews
Bevor Sie ein Array-Problem programmieren, gehen Sie diese gedankliche Checkliste durch:
- Ist das Array sortiert? (Ermöglicht zwei Zeiger und binäre Suche)
- Sind die Werte begrenzt (z. B. 1..n)? (Ermöglicht indexbasierte Tricks)
- Ist In-Place-Verarbeitung erforderlich? (Lese-Schreib-Zeiger oder Vertauschungen)
- Benötige ich alle Paare oder nur eines? (Beeinflusst, ob verschachtelte Schleifen zulässig sind)
- Randfälle: leeres Array, einzelnes Element, nur gleiche Werte
def max_profit(prices):
# Pattern: single scan, track running minimum
# Time: O(n), Space: O(1)
if not prices: return 0 # edge case: empty
min_price = prices[0]
max_prof = 0
for price in prices[1:]: # start at index 1
max_prof = max(max_prof, price - min_price)
min_price = min(min_price, price)
return max_prof
print(max_profit([7, 1, 5, 3, 6, 4])) # 5
print(max_profit([7, 6, 4, 3, 1])) # 0Kadane-Algorithmus: Maximales Subarray
Der Kadane-Algorithmus findet das zusammenhängende Subarray mit der maximalen Summe in O(n) Zeit und mit O(1) Speicherplatz. Entscheiden Sie in jedem Schritt, ob Sie das aktuelle Subarray erweitern oder ein neues beginnen: current = max(num, current + num). Wenn current + num kleiner ist als num allein, verschlechtert das aktuelle Subarray das Ergebnis, und Sie beginnen neu. Verfolgen Sie währenddessen das globale Maximum.
def max_subarray(nums):
current = global_max = nums[0]
for n in nums[1:]:
current = max(n, current + n) # extend or restart
global_max = max(global_max, current)
return global_max
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# 6 (subarray [4, -1, 2, 1])
print(max_subarray([-1, -2, -3]))
# -1 (all negative: take the least negative)Schnelltest
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Arrays bieten einen wahlfreien Zugriff in O(1), aber Einfüge- und Löschvorgänge in der Mitte benötigen O(n) – diese Asymmetrie hilft bei der Wahl des Algorithmus, das Lese-Schreib-Zeiger-Muster entfernt Elemente oder verschiebt Werte in-place in O(n) Zeit und mit O(1) Speicherplatz und die Kodierung über das Vorzeichenbit sowie Tricks mit dem Index als Markierung ermöglichen Lösungen mit O(1) Speicherplatz für Probleme, die andernfalls ein zusätzliches Array erfordern würden. Als Nächstes sehen wir uns Präfixsummen und laufende Summen an.
Häufig gestellte Fragen
Ist die Lektion „Array-Grundlagen und In-Place-Operationen“ kostenlos?
Ja — der vollständige Text von „Array-Grundlagen und In-Place-Operationen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Array-Grundlagen und In-Place-Operationen“?
Wiederholen Sie Indizierung und Mutation und lernen Sie die häufigsten Array-Fallen in Interviews kennen, etwa Off-by-one-Fehler und das Ändern einer Liste während der Iteration. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Array-Grundlagen und In-Place-Operationen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Array-Grundlagen und In-Place-Operationen
- Präfixsummen und laufende Summen
- Zwei Zeiger: entgegengesetzte Enden
- Zwei Zeiger: langsam und schnell