Основы массивов и операции на месте
Повторите индексацию и изменение данных и разберите распространённые ошибки в задачах на собеседованиях, например ошибки на единицу и изменение списка во время итерации
«Основы массивов и операции на месте» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Массивы как непрерывная память
Внутри Python-список основан на динамическом массиве — непрерывном блоке памяти, где элементы хранятся по последовательным адресам. Такая организация обеспечивает произвольный доступ по индексу за O(1): Python мгновенно вычисляет address = base + index × element_size. Вставка или удаление в середине требует сдвинуть все последующие элементы, что стоит O(n). Эта асимметрия лежит в основе большинства обсуждений компромиссов при работе с массивами на собеседованиях.
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]Ошибка смещения на единицу: классическая ошибка с массивами
Ошибки смещения на единицу — самый частый источник неправильных ответов в задачах на массивы. Индексация Python с нуля означает, что последний допустимый индекс равен len(arr) - 1. При написании циклов определяйте, нужно ли использовать < или <=, проверяя граничное условие на минимальном допустимом входе (n=1 или n=2). Перед отправкой решения всегда проверяйте границу на конкретных примерах.
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)]Разворот на месте с помощью двух указателей
Разворот массива на месте выполняется с помощью двух указателей, начинающих движение с противоположных концов, и обмена элементов по направлению к центру, пока указатели не встретятся. Для этого требуется O(1) дополнительной памяти и O(n) времени. Условие left < right (строгое неравенство) обеспечивает корректность как для чётной, так и для нечётной длины: при нечётном числе элементов центральный элемент автоматически остаётся на месте.
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 unchangedПоворот массива на месте
Повернуть массив вправо на k позиций можно на месте, развернув три сегмента: сначала разверните весь массив, затем первые k элементов, а потом оставшиеся n-k элементов. Это даёт O(n) времени и O(1) памяти — гораздо лучше, чем подход со срезами и объединением, требующий O(n) памяти. Всегда уменьшайте k по модулю n, чтобы обработать случай 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]Удаление элементов на месте
Удаление дубликатов или целевых значений на месте выполняется с помощью указателя записи, который отслеживает позицию, куда нужно записать следующий допустимый элемент. Указатель чтения просматривает элементы слева направо; найдя допустимый элемент, он копирует его на позицию записи, после чего оба указателя продвигаются. Это основной шаблон для задач LeetCode, таких как «удаление элемента», «удаление дубликатов из отсортированного массива» и «перемещение нулей».
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]Перемещение нулей: указатель чтения и записи
Переместите все нули в конец массива, сохранив порядок ненулевых элементов. Подход с указателем чтения и записи помещает каждый ненулевой элемент на позицию записи, а затем заполняет хвост нулями. Альтернативный подход перемещает нули назад с помощью обменов, сохраняя порядок без второго прохода заполнения. Оба метода работают за O(n) времени и используют O(1) памяти.
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]Возведение в квадрат и сортировка на месте
Если дан отсортированный массив целых чисел, среди которых могут быть отрицательные, верните массив их квадратов в отсортированном порядке. Наивный подход сначала возводит числа в квадрат, а затем сортирует их: O(n log n). Оптимальный подход с двумя указателями использует тот факт, что самые большие квадраты получаются на одном из концов отсортированного входного массива: сравнивайте абсолютные значения крайних левого и правого элементов и заполняйте результат справа налево за 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]Поиск опорного элемента и разбиение
Задача о голландском национальном флаге разделяет массив на три секции (меньше опорного элемента, равные ему и больше него) на месте с помощью трёх указателей. Это ключевой подэтап быстрой сортировки и решение задачи LeetCode «sort colors». Инвариант, согласно которому элементы перед указателем с меньшим индексом меньше опорного элемента, а элементы после указателя с большим индексом больше опорного элемента, определяет работу алгоритма.
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]Изменение элементов массива во время итерации
Вы можете безопасно изменять значения элементов (например, умножать их на -1, чтобы пометить посещённые элементы) во время итерации, но никогда не изменяйте длину списка во время цикла for. Безопасный приём кодирования: временно кодируйте два значения в одном целом числе (например, используя бит знака), чтобы имитировать дополнительное логическое значение для каждого элемента без выделения дополнительной памяти. Это встречается в задачах вроде «найти все числа, которые отсутствуют в массиве».
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 spaceКонтрольный список шаблонов для собеседований по массивам
Перед написанием кода для любой задачи на массивы пройдите по этому мысленному контрольному списку:
- Массив отсортирован? (это позволяет использовать два указателя и двоичный поиск)
- Значения элементов ограничены (например, диапазоном 1..n)? (это позволяет применять приёмы на основе индексов)
- Требуется ли работа на месте? (указатель чтения и записи или обмены)
- Нужны ли все пары или только одна? (это определяет, допустимы ли вложенные циклы)
- Граничные случаи: пустой массив, один элемент, одинаковые значения
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])) # 0Алгоритм Кадане: максимальный подмассив
Алгоритм Кадане находит непрерывный подмассив с максимальной суммой за O(n) времени и использует O(1) памяти. На каждом шаге решайте, расширить ли текущий подмассив или начать новый: current = max(num, current + num). Если current + num меньше, чем один только num, текущий подмассив уменьшает результат, поэтому начинайте заново. В течение всего прохода отслеживайте глобальный максимум.
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)Быстрая проверка
Проверьте, насколько вы поняли концепции «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке вы узнали: массивы обеспечивают произвольный доступ за O(1), но вставка и удаление в середине занимают O(n) — знание этой асимметрии помогает выбирать алгоритм, шаблон указателя чтения и записи позволяет удалять элементы или перемещать значения на месте за O(n) времени и O(1) памяти, а кодирование с помощью бита знака и приёмы с пометкой через индекс позволяют решать за O(1) памяти задачи, для которых иначе потребовался бы вспомогательный массив. Далее мы рассмотрим префиксные суммы и нарастающие итоги.
Часто задаваемые вопросы
Урок «Основы массивов и операции на месте» бесплатный?
Да — полный текст урока «Основы массивов и операции на месте» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Основы массивов и операции на месте»?
Повторите индексацию и изменение данных и разберите распространённые ошибки в задачах на собеседованиях, например ошибки на единицу и изменение списка во время итерации Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Основы массивов и операции на месте»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Основы массивов и операции на месте
- Префиксные суммы и текущие итоги
- Два указателя: от противоположных концов
- Два указателя: медленный и быстрый