C++: подробное руководство по массивам

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

1. Введение в массивы

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

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

Объявление и инициализация

// Объявление
int arr[10];

// Инициализация
int arr[] = {1, 2, 3, 4, 5};

Ключевые моменты:

• Индексация начинается с 0.
• В статических массивах размер  —  это константное выражение.

2. Базовые операции

Доступ к элементам

Доступ к элементам выполняется по индексу:

Обход

Массивы перебираются с помощью циклов:

for(int i = 0; i < size; i++) {
    cout << arr[i] << " ";
}

Вставка и удаление

• Вставка: размеры статических массивов фиксированы, нельзя вставлять элементы сверх границ емкости массивов.
• Удаление: элементов сопровождается перемещением последующих элементов.

3. Основные алгоритмы

Алгоритмы поиска

• Линейный поиск: O(n).

int linearSearch(int arr[], int size, int target) {
    for(int i = 0; i < size; i++) {
        if(arr[i] == target)
            return i;
    }
    return -1;
}

• Двоичный поиск O(log n)  —  требуется отсортированный массив.

int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(arr[mid] == target)
            return mid;
        else if(arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

Алгоритмы сортировки

• Сортировка пузырьком.
• Сортировка выбором.
• Сортировка вставками.
• Сортировка слиянием.
• Быстрая сортировка.

Полезно знать хотя бы один эффективный алгоритм сортировки, например сортировку слиянием или быструю сортировку.

4. Продвинутые концепции

Многомерные массивы

Из них создаются матрицы и сетки.

int matrix[3][4]; // три стоки, четыре столбца

Динамические массивы, векторы

На C++ возможности динамических массивов доступны благодаря std::vector.

#include <vector>

std::vector<int> vec;
vec.push_back(10);
vec.pop_back();

5. Алгоритмические шаблоны

Метод двух указателей

Им решаются задачи, связанные с парами в отсортированном массиве.

int left = 0, right = size - 1;
while(left < right) {
    // Обрабатываются элементы в «arr[left]» и «arr[right]»
}

Пример задачи: найти два числа, сумма которых равна заданной.

Метод скользящего окна

Идеален для задач, связанных с подмассивами.

int windowSize = k;
for(int i = 0; i < size - windowSize + 1; i++) {
    // Обрабатывается подмассив от «arr[i]» до «arr[i + windowSize - 1]»
}

Пример задачи: найти максимальную сумму подмассива размером k.

Префиксная сумма

Ею эффективно вычисляется сумма элементов в диапазоне.

int prefixSum[size];
prefixSum[0] = arr[0];
for(int i = 1; i < size; i++) {
    prefixSum[i] = prefixSum[i - 1] + arr[i];
}

6. Вопросы собеседования с решениями

Пример задачи 1. Поменять порядок элементов массива на обратный

Требуется: поменять порядок элементов массива на обратный.

Решение:

void reverseArray(int arr[], int size) {
    int left = 0, right = size - 1;
    while(left < right) {
        std::swap(arr[left], arr[right]);
        left++;
        right--;
    }
}

Ключевые понятия:

• Два указателя.
• Алгоритм на месте.

Пример задачи 2. Найти максимальную сумму подмассива, это алгоритм Kadane

Требуется: найти непрерывный подмассив с максимальной суммой.

Решение:

int maxSubArraySum(int arr[], int size) {
    int maxSoFar = arr[0], maxEndingHere = arr[0];
    for(int i = 1; i < size; i++) {
        maxEndingHere = std::max(arr[i], maxEndingHere + arr[i]);
        maxSoFar = std::max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}

Ключевые понятия:

• Динамическое программирование.
• «Жадный» подход.

Пример задачи 3. Удаление дублей из отсортированного массива

Требуется: удалить дубли на месте и вернуть новую длину.

Решение:

int removeDuplicates(int arr[], int size) {
    if(size == 0) return 0;
    int index = 1;
    for(int i = 1; i < size; i++) {
        if(arr[i] != arr[i - 1]) {
            arr[index++] = arr[i];
        }
    }
    return index;
}

Ключевые понятия:

• Изменение на месте.
• Эффективное использование пространства.

7. Рекомендации

Управление памятью

• Чтобы избежать ошибок сегментации, будьте осторожны с границами массива.
• При использовании динамической памяти  —  new и delete  —  убедитесь, что для каждого new имеется соответствующий delete.

Оптимизация

• Избегайте лишних вычислений: сохраняйте переиспользуемые результаты.
• Используйте соответствующие структуры данных: иногда с std::vector или другими контейнерами производительность выше.

Заключение

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

Что дальше:

• Реализуйте примеры задач самостоятельно.
• Изучайте более сложные задачи, связанные с массивами.
• Читайте о временно́й и пространственной сложности алгоритмов.

Читайте также:

• Перестановка чисел в C++: руководство
• Оптимизация кода задачи на миллиард строк — ускоряем запуск в 87 раз
• C++: подробно о реализации двусторонней очереди

Читайте нас в Telegram, VK и Дзен

---

Перевод статьи Ranjan Monisha: Mastering Arrays in C++: A Comprehensive Guide for Aspiring Programmers