Grunnleggende om arrays og in-place-operasjoner
Repeter indeksering, mutasjon og de vanligste fallgruvene i array-intervjuer, som feil med én avvik og endring av en liste under iterasjon.
Grunnleggende om arrays og in-place-operasjoner er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 1 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i DSA Interview Prep, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Arrayer som sammenhengende minne
Under panseret støttes en Python-liste av en dynamisk array – en sammenhengende minneblokk der elementene lagres på fortløpende adresser. Denne utformingen gir O(1) tilfeldig tilgang via indeks: Python beregner address = base + index × element_size umiddelbart. Innsettinger eller slettinger i midten krever at alle etterfølgende elementer flyttes, noe som koster O(n). Denne asymmetrien er opphavet til de fleste diskusjoner om avveininger ved array-oppgaver i intervjuer.
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: den klassiske array-feilen
Off-by-one-feil er den vanligste kilden til gale svar i array-oppgaver. Pythons 0-baserte indeksering betyr at siste gyldige indeks er len(arr) - 1. Når De skriver løkker, avgjør om De trenger < eller <= ved å kontrollere grensebetingelsen med den minste gyldige inndataen (n=1 eller n=2). Spor alltid grensen med konkrete eksempler før De sender inn.
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)]Reversering på stedet med to pekere
Reversering av en array på stedet bruker to pekere som starter i hver sin ende og bytter elementer innover til de møtes. Dette krever O(1) ekstra plass og O(n) tid. Betingelsen left < right (strengt mindre enn) sikrer korrekthet for både jevne og odde lengder – med et oddetall elementer blir det midterste elementet automatisk stående på plass.
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 unchangedRotere en array på stedet
Å rotere en array k posisjoner mot høyre kan gjøres på stedet ved å reversere tre segmenter: reverser hele arrayen, deretter de første k elementene og så de resterende n-k elementene. Dette gir O(n) tid og O(1) plass – langt bedre enn O(n)-plass-tilnærmingen med slicing og sammenkobling. Reduser alltid k modulo n for å håndtere k ≥ n.
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]Fjerne elementer på stedet
Å fjerne duplikater eller målverdier på stedet bruker en skrivepeker som holder styr på hvor neste gyldige element skal skrives. Lesepekeren skanner fremover; når den finner et gyldig element, kopierer den det til skriveposisjonen og flytter begge pekerne fremover. Dette er kjernemønsteret i LeetCode-oppgaver som 'remove element', 'remove duplicates from sorted array' og '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]Flytt nuller: lese-/skrivepeker
Flytt alle nuller til slutten av en tabell, samtidig som rekkefølgen på elementene som ikke er null, bevares. Tilnærmingen med en lese-/skrivepeker plasserer hvert element som ikke er null, på skriveposisjonen og fyller deretter resten med nuller. En alternativ tilnærming flytter nuller bakover ved å bytte om elementer. Da bevares rekkefølgen uten en ekstra utfyllingsrunde. Begge bruker O(n) tid og O(1) plass.
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]Kvadrer og sorter in-place
Gitt en sortert tabell med heltall (som kan være negative), skal du returnere en tabell med kvadratene i sortert rekkefølge. Den naive tilnærmingen kvadrerer først og sorterer deretter: O(n log n). Den optimale topekerstilnærmingen utnytter at de største kvadratene kommer fra en av endene i den sorterte inndataen: sammenlign absoluttverdiene til elementene lengst til venstre og høyre, og fyll resultatet fra høyre mot venstre på O(n) tid.
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]Finne pivot og partisjonere
Det nederlandske flaggproblemet partisjonerer en tabell på stedet i tre deler (mindre enn, lik og større enn pivoten) ved hjelp av tre pekere. Dette er det viktige delsteget i quicksort og løsningen på LeetCode-problemet «sort colors». Ved å opprettholde invarianten om at elementene før low-pekeren er < pivot, og at elementene etter high-pekeren er > pivot, drives algoritmen fremover.
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]Endre matriselementer under iterering
Du kan trygt endre elementverdier (for eksempel multiplisere med -1 for å markere besøkte elementer) mens du itererer, men endre aldri lengden på en liste i en for-løkke. Et trygt kodingstriks er å kode to verdier midlertidig i ett heltall (for eksempel ved å bruke fortegnsbiten) for å simulere en ekstra boolsk verdi per element uten å allokere mer plass. Dette dukker opp i problemer som «finn alle tallene som mangler i en tabell».
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 spaceSjekkliste for tabellmønstre i intervjuer
Før du skriver kode for et tabellproblem, gå gjennom denne mentale sjekklisten:
- Er tabellen sortert? (muliggjør to pekere og binærsøk)
- Er elementene begrenset (for eksempel 1..n)? (muliggjør indeksbaserte triks)
- Må løsningen være in-place? (lese-/skrivepeker eller bytteoperasjoner)
- Trenger jeg alle par eller bare ett? (påvirker om nestede løkker er akseptable)
- Grensetilfeller: tom tabell, ett element, bare like verdier
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])) # 0Kadanes algoritme: Maksimal deltabell
Kadanes algoritme finner den sammenhengende deltabellen med størst sum på O(n) tid og med O(1) plass. Ved hvert trinn avgjør du om den gjeldende deltabellen skal utvides, eller om en ny skal startes: current = max(num, current + num). Hvis current + num er mindre enn num alene, trekker den gjeldende deltabellen oss ned, og vi starter på nytt. Hold oversikt over det globale maksimumet underveis.
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)Hurtigsjekk
Test forståelsen din av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte du at: tabeller gir O(1) tilfeldig aksess, men innsettinger og slettinger i midten tar O(n) — denne asymmetrien hjelper deg med å velge algoritme, mønsteret med lese-/skrivepeker fjerner elementer eller flytter verdier på stedet på O(n) tid og med O(1) plass, og koding med fortegnsbit og bruk av indeks som markør muliggjør løsninger med O(1) plass for problemer som ellers ville krevd en hjelpetabell. Neste tema er prefikssummer og løpende summer.
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Grunnleggende om arrays og in-place-operasjoner» gratis?
Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «Grunnleggende om arrays og in-place-operasjoner», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Hva lærer jeg i «Grunnleggende om arrays og in-place-operasjoner»?
Repeter indeksering, mutasjon og de vanligste fallgruvene i array-intervjuer, som feil med én avvik og endring av en liste under iterasjon. Du øver på DSA Interview Prep med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med DSA Interview Prep?
Ingen tidligere erfaring er nødvendig. DSA Interview Prep på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «Grunnleggende om arrays og in-place-operasjoner»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne DSA Interview Prep-leksjonen?
Ja. Alle DSA Interview Prep-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Grunnleggende om arrays og in-place-operasjoner
- Prefikssummer og løpende totaler
- To pekere: motsatte ender
- To pekere: langsom og rask