Podstawy tablic i operacje w miejscu
Powtórzą Państwo indeksowanie i modyfikowanie danych oraz najczęstsze pułapki rekrutacyjne związane z tablicami, takie jak błędy off-by-one i modyfikowanie listy podczas iteracji.
Podstawy tablic i operacje w miejscu to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Tablice jako ciągły obszar pamięci
Wewnętrznie lista w Pythonie jest oparta na tablicy dynamicznej — ciągłym bloku pamięci, w którym elementy są przechowywane pod kolejnymi adresami. Taki układ zapewnia dostęp losowy O(1) za pomocą indeksu: Python natychmiast oblicza address = base + index × element_size. Wstawianie lub usuwanie elementów ze środka wymaga przesunięcia wszystkich kolejnych elementów, co kosztuje O(n). Ta asymetria jest źródłem większości dyskusji o kompromisach dotyczących tablic podczas rozmów kwalifikacyjnych.
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]Błędy off-by-one: klasyczny błąd w zadaniach z tablicami
Błędy off-by-one są najczęstszym źródłem niepoprawnych odpowiedzi w zadaniach dotyczących tablic. Indeksowanie od zera w Pythonie oznacza, że ostatnim poprawnym indeksem jest len(arr) - 1. Podczas pisania pętli należy ustalić, czy potrzebny jest operator <, czy <=, sprawdzając warunek brzegowy dla najmniejszych poprawnych danych wejściowych (n=1 lub n=2). Przed przesłaniem rozwiązania zawsze należy prześledzić warunek brzegowy na konkretnych przykładach.
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)]Odwracanie w miejscu za pomocą dwóch wskaźników
Odwracanie tablicy w miejscu polega na użyciu dwóch wskaźników rozpoczynających pracę na przeciwnych końcach i zamieniających elementy, aż się spotkają. Wymaga to O(1) dodatkowej pamięci i O(n) czasu. Warunek left < right (ściśle mniejsze) zapewnia poprawność zarówno dla długości parzystych, jak i nieparzystych — przy nieparzystej liczbie elementów środkowy element automatycznie pozostaje na swoim miejscu.
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 unchangedObracanie tablicy w miejscu
Obrót tablicy w prawo o k pozycji można wykonać w miejscu przez odwrócenie trzech segmentów: najpierw całej tablicy, następnie pierwszych k elementów, a na końcu pozostałych n-k elementów. Daje to O(n) czasu i O(1) pamięci — znacznie lepiej niż podejście wymagające O(n) pamięci, oparte na operacjach slicing i konkatenacji. Zawsze należy zredukować k modulo n, aby obsłużyć przypadek 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]Usuwanie elementów w miejscu
Usuwanie duplikatów lub wartości docelowych w miejscu wykorzystuje wskaźnik zapisu, który wskazuje, gdzie należy zapisać następny poprawny element. Wskaźnik odczytu przesuwa się do przodu; gdy znajdzie poprawny element, kopiuje go na pozycję wskazywaną przez wskaźnik zapisu, po czym oba wskaźniki przesuwają się dalej. To podstawowy schemat zadań LeetCode, takich jak 'remove element', 'remove duplicates from sorted array' i '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]Przenoszenie zer: wskaźnik odczytu i zapisu
Należy przenieść wszystkie zera na koniec tablicy, zachowując kolejność elementów niezerowych. Podejście ze wskaźnikiem odczytu i zapisu umieszcza każdy element niezerowy na pozycji zapisu, a następnie wypełnia końcówkę zerami. Alternatywne podejście przesuwa zera wstecz za pomocą zamian, zachowując kolejność bez drugiego przejścia wypełniającego. Oba rozwiązania działają w czasie O(n) i zużywają O(1) pamięci.
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]Podnoszenie do kwadratu i sortowanie w miejscu
Mając posortowaną tablicę liczb całkowitych (które mogą być ujemne), należy zwrócić tablicę ich kwadratów w posortowanej kolejności. Naiwne podejście najpierw podnosi elementy do kwadratu, a potem je sortuje: O(n log n). Optymalne podejście z dwoma wskaźnikami wykorzystuje fakt, że największe kwadraty pochodzą z jednego z końców posortowanego wejścia: porównuje wartości bezwzględne skrajnych elementów i wypełnia wynik od prawej do lewej w czasie O(n).
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]Znajdowanie pivota i partycjonowanie
Problem flagi holenderskiej dzieli tablicę na trzy sekcje (elementy mniejsze od pivota, równe pivotowi i większe od pivota) w miejscu, używając trzech wskaźników. To kluczowy podkrok sortowania szybkiego i rozwiązanie zadania LeetCode 'sort colors'. Utrzymywanie niezmiennika, zgodnie z którym elementy przed wskaźnikiem low są < pivot, a elementy za wskaźnikiem high są > pivot, wyznacza działanie algorytmu.
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]Modyfikowanie elementów tablicy podczas iterowania
Można bezpiecznie modyfikować wartości elementów (np. mnożyć je przez -1, aby oznaczyć odwiedzone), ale nigdy nie należy zmieniać długości listy podczas pętli for. Bezpieczna sztuczka kodowania polega na tymczasowym zakodowaniu dwóch wartości w jednej liczbie całkowitej (np. za pomocą bitu znaku), aby zasymulować dodatkową wartość logiczną dla każdego elementu bez przydzielania dodatkowej pamięci. Pojawia się to w zadaniach takich jak „znajdź wszystkie liczby, które zniknęły z tablicy”.
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 spaceLista kontrolna wzorców zadań rekrutacyjnych dotyczących tablic
Przed rozpoczęciem kodowania dowolnego zadania dotyczącego tablic należy przejść przez następującą listę kontrolną:
- Czy tablica jest posortowana? (umożliwia użycie dwóch wskaźników i wyszukiwania binarnego)
- Czy elementy mają ograniczony zakres (np. 1..n)? (umożliwia sztuczki wykorzystujące indeksy)
- Czy wymagane jest działanie w miejscu? (wskaźnik odczytu i zapisu lub zamiany)
- Czy potrzebne są wszystkie pary, czy tylko jedna? (wpływa na to, czy zagnieżdżone pętle są akceptowalne)
- Przypadki brzegowe: pusta tablica, jeden element, same jednakowe wartości
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])) # 0Algorytm Kadane’a: maksymalna podtablica
Algorytm Kadane’a znajduje spójną podtablicę o największej sumie w czasie O(n) i przy użyciu O(1) pamięci. Na każdym kroku należy zdecydować, czy rozszerzyć bieżącą podtablicę, czy rozpocząć nową: current = max(num, current + num). Jeśli current + num jest mniejsze niż samo num, bieżąca podtablica obniża wynik, więc należy rozpocząć od nowa. Przez cały czas należy śledzić maksimum globalne.
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)Szybki sprawdzian
Proszę sprawdzić swoją znajomość pojęć Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji omówiono: tablice zapewniają dostęp losowy w czasie O(1), ale wstawianie i usuwanie elementów w środku zajmuje O(n) — znajomość tej asymetrii pomaga wybrać algorytm, wzorzec wskaźnika odczytu i zapisu usuwa elementy lub przenosi wartości w miejscu w czasie O(n) i przy użyciu O(1) pamięci oraz kodowanie bitem znaku i sztuczki wykorzystujące indeks jako znacznik umożliwiają rozwiązania problemów w O(1) pamięci, które w przeciwnym razie wymagałyby dodatkowej tablicy. Następnie omówimy sumy prefiksowe i sumy bieżące.
Często zadawane pytania
Czy lekcja „Podstawy tablic i operacje w miejscu” jest bezpłatna?
Tak — pełny tekst „Podstawy tablic i operacje w miejscu” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Podstawy tablic i operacje w miejscu”?
Powtórzą Państwo indeksowanie i modyfikowanie danych oraz najczęstsze pułapki rekrutacyjne związane z tablicami, takie jak błędy off-by-one i modyfikowanie listy podczas iteracji. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „Podstawy tablic i operacje w miejscu”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Podstawy tablic i operacje w miejscu
- Sumy prefiksowe i sumy narastające
- Dwa wskaźniki: przeciwległe końce
- Dwa wskaźniki: wolny i szybki