EasyТеория9 min

Массивы: основы

Статические и динамические массивы, базовые операции и их сложность

AlgoArrays and strings

Что такое массив?

Массив — это непрерывный блок памяти, хранящий элементы одного типа. Это самая базовая и часто используемая структура данных.

Индексы:    0     1     2     3     4
          +-----+-----+-----+-----+-----+
Значения: | 10  | 20  | 30  | 40  | 50  |
          +-----+-----+-----+-----+-----+
Адреса:   0x100 0x104 0x108 0x10C 0x110
          (каждый int занимает 4 байта)

Ключевое свойство: адрес элемента = базовый_адрес + индекс * размер_элемента. Поэтому доступ по индексу — O(1).

Статические vs динамические массивы

Статический массив

Размер фиксирован при создании. Нельзя увеличить или уменьшить.

// PHP: SplFixedArray — fixed-size array
$arr = new SplFixedArray(5); // [null, null, null, null, null]
$arr[0] = 10;
// Cannot grow beyond initial size
### Динамический массив

Автоматически увеличивается при добавлении элементов.

// PHP: array — dynamic array
$arr = [];
$arr[] = 10;  // [10]
$arr[] = 20;  // [10, 20]
$arr[] = 30;  // [10, 20, 30]
// Size increases automatically
### Как работает рост динамического массива 
Начальная ёмкость: 4
[10, 20, 30, _]     <- есть место, append = O(1)
[10, 20, 30, 40]    <- массив полон

Добавляем 50:
1. Создаём новый массив ёмкостью 8 (обычно x2)
2. Копируем все элементы: O(n)
3. Добавляем новый элемент

[10, 20, 30, 40, 50, _, _, _]  <- новая ёмкость 8

Амортизированная сложность append: O(1)

Операции и их сложность

Операция Сложность Пояснение
Доступ по индексу arr[i] O(1) Прямой расчёт адреса
Поиск элемента O(n) Нужно проверить каждый элемент
Вставка в конец (append) O(1)* Амортизированно
Вставка в начало O(n) Сдвиг всех элементов вправо
Вставка в середину O(n) Сдвиг элементов после позиции вставки
Удаление с конца (pop) O(1) Просто уменьшаем размер
Удаление из начала O(n) Сдвиг всех элементов влево
Удаление из середины O(n) Сдвиг элементов

Визуализация вставки в середину:

Вставить 25 на позицию 2:

До:  [10, 20, 30, 40, 50]
              ^
      Сдвигаем 30, 40, 50 вправо:

Шаг: [10, 20, __, 30, 40, 50]
              ^
      Записываем 25:

После: [10, 20, 25, 30, 40, 50]

Базовые операции в PHP

Создание и инициализация

$arr = [1, 2, 3, 4, 5];                      // Literal
$zeros = array_fill(0, 10, 0);               // 10 zeros
$matrix = [];
for ($i = 0; $i < 3; $i++) {
    $matrix[$i] = array_fill(0, 3, 0);       // 3x3 matrix
}
$ranged = range(1, 10);                       // [1, 2, ..., 10]
### Обход массива 
// By value
foreach ($arr as $x) {
    echo $x . "\n";
}

// By index and value
foreach ($arr as $i => $x) {
    echo "arr[$i] = $x\n";
}

// In reverse order
for ($i = count($arr) - 1; $i >= 0; $i--) {
    echo $arr[$i] . "\n";
}
### Срезы (slicing) 
$arr = [10, 20, 30, 40, 50];
array_slice($arr, 1, 2);     // [20, 30]       — from index 1, take 2
array_slice($arr, 0, 3);     // [10, 20, 30]   — first 3
array_slice($arr, 2);        // [30, 40, 50]   — from index 2 to end
array_slice($arr, -2);       // [40, 50]       — last 2
array_reverse($arr);         // [50, 40, 30, 20, 10]  — reverse
> **Запомни:** В PHP `array_slice()` создаёт **копию** — это O(k) по памяти, где k — размер среза.

Строки как массивы

Строки — это по сути массивы символов (с некоторыми отличиями).

// PHP: strings are mutable, accessible by index
$s = 'hello';
echo $s[0];       // 'h'
$s[0] = 'H';      // 'Hello' — strings ARE mutable in PHP

// Useful string functions
strpos($s, 'll');           // 2 (index of substring)
substr_count($s, 'l');      // 2
explode(',', 'a,b,c');      // split by delimiter -> ['a', 'b', 'c']

// For multibyte (Unicode) strings use mb_* functions
$s = 'привет';
mb_strlen($s);              // 6
mb_substr($s, 0, 1);        // 'п'
## Типичные задачи на массивы

Разворот массива

// O(n) time, O(1) memory
function reverseArray(array &$arr): void
{
    $left = 0;
    $right = count($arr) - 1;
    while ($left < $right) {
        [$arr[$left], $arr[$right]] = [$arr[$right], $arr[$left]];
        $left++;
        $right--;
    }
}
### Удаление дубликатов из отсортированного массива 
// In-place, O(1) extra memory
function removeDuplicates(array &$arr): int
{
    if (empty($arr)) {
        return 0;
    }
    $write = 1;
    for ($read = 1; $read < count($arr); $read++) {
        if ($arr[$read] !== $arr[$read - 1]) {
            $arr[$write] = $arr[$read];
            $write++;
        }
    }
    return $write; // Length of unique part
}
// Example: [1,1,2,2,3] -> [1,2,3,...] returns 3
### Поворот массива 
// Rotate array to the right by k positions
// [1,2,3,4,5], k=2 -> [4,5,1,2,3]
function rotate(array &$arr, int $k): void
{
    $n = count($arr);
    $k = $k % $n; // In case k > n

    $reverse = function (int $start, int $end) use (&$arr): void {
        while ($start < $end) {
            [$arr[$start], $arr[$end]] = [$arr[$end], $arr[$start]];
            $start++;
            $end--;
        }
    };

    $reverse(0, $n - 1);     // [5,4,3,2,1]
    $reverse(0, $k - 1);     // [4,5,3,2,1]
    $reverse($k, $n - 1);    // [4,5,1,2,3]
}
## Многомерные массивы (матрицы) 
// Create 3x4 matrix
$rows = 3;
$cols = 4;
$matrix = [];
for ($i = 0; $i < $rows; $i++) {
    $matrix[$i] = array_fill(0, $cols, 0);
}

// Traverse matrix
for ($i = 0; $i < $rows; $i++) {
    for ($j = 0; $j < $cols; $j++) {
        echo $matrix[$i][$j] . ' ';
    }
    echo "\n";
}
``` Матрица 3x4: col 0 col 1 col 2 col 3 row 0: [ 1, 2, 3, 4 ] row 1: [ 5, 6, 7, 8 ] row 2: [ 9, 10, 11, 12 ]

matrix[1][2] = 7 (строка 1, столбец 2)


> **Запомни:** Массив — это основа всего. Знание сложности операций критически важно: доступ по индексу O(1), поиск O(n), вставка/удаление в начале O(n). Для интервью — освой паттерны Two Pointers, Sliding Window и Prefix Sum (следующие главы).

## Итоги

1. Массив = непрерывная память, доступ по индексу O(1)
2. Динамические массивы растут автоматически, append амортизированно O(1)
3. Вставка/удаление не с конца — O(n) из-за сдвига элементов
4. Строки в PHP — изменяемые (mutable), но для Unicode используй mb_* функции
5. `array_slice()` в PHP создаёт копии
6. Для интервью: знай как делать reverse, remove duplicates, rotate in-place

Проверь себя

Какова сложность вставки элемента в начало массива (array_unshift) из n элементов?

Что произойдёт при доступе к символу Unicode-строки по индексу? ```php $s = 'привет'; echo $s[0]; ```

Как работает алгоритм поворота массива через три разворота? ```php // [1,2,3,4,5], k=2 $reverse(0, $n-1); // Шаг 1 $reverse(0, $k-1); // Шаг 2 $reverse($k, $n-1); // Шаг 3 ```

Что вернёт функция removeDuplicates для отсортированного массива [1, 1, 2, 2, 3, 3, 3]?

Связанные темы

Быстрая сортировка

Связанная тема