Массивы

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

Держать десятки отдельных переменных неудобно.

JavaC++PythonОтличия

Для этого в Java есть массивы.

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

int[] a = new int[5];  // массив из 5 целых чисел: a[0], a[1], ..., a[4]

Основное

Одномерный массив целых чисел:

int[] a = new int[n];      // создать массив длины n
a[i] = 10;                 // записать значение в ячейку с индексом i
int x = a[i];              // прочитать значение из ячейки
int len = a.length;        // длина массива

Важно:

индексы идут от 0 до a.length - 1;
при выходе за границы (a[-1], a[n]) будет ошибка во время работы программы;
все элементы нового int[] по умолчанию равны 0.

Идея массива

Без массива:

int x1, x2, x3, x4, x5;
// неудобно и легко запутаться

С массивом:

int[] a = new int[5];  // 5 целых чисел

Теперь можно обращаться к элементам по индексу:

a[0] = 10;
a[1] = 20;
a[2] = 30;

Объявление и создание массива

Общий шаблон:

тип[] имя = new тип[длина];

Примеры:

int n = 10;
int[] a = new int[n];       // массив целых чисел

double[] x = new double[5]; // массив из 5 дробных чисел

boolean[] used = new boolean[100]; // массив логических значений

Сначала указываем тип элементов и [], затем имя массива, затем создаём массив нужной длины через new.

Чтение массива из ввода

Частый случай: сначала во входе дано число n — сколько элементов, а затем n чисел.

import java.util.Scanner;

public class ReadArrayExample {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();      // количество элементов
        int[] a = new int[n];      // создаём массив

        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();   // читаем i-й элемент
        }

        // вывод массива
        for (int i = 0; i < n; i++) {
            System.out.println(a[i]);
        }
    }
}

Ввод

5
10 20 30 40 50

Вывод

Важный момент: цикл по индексу почти всегда идёт от 0 до n - 1.

Примеры и типичные шаблоны

Сумма элементов массива

int n = in.nextInt();
int[] a = new int[n];

for (int i = 0; i < n; i++) {
    a[i] = in.nextInt();
}

int sum = 0;
for (int i = 0; i < n; i++) {
    sum = sum + a[i];   // или sum += a[i];
}

System.out.println(sum);

Минимум и максимум в массиве

int n = in.nextInt();
int[] a = new int[n];

for (int i = 0; i < n; i++) {
    a[i] = in.nextInt();
}

int min = a[0];
int max = a[0];

for (int i = 1; i < n; i++) {
    if (a[i] < min) {
        min = a[i];
    }
    if (a[i] > max) {
        max = a[i];
    }
}

System.out.println("min = " + min);
System.out.println("max = " + max);

Подсчёт количества элементов по условию

int n = in.nextInt();
int[] a = new int[n];

for (int i = 0; i < n; i++) {
    a[i] = in.nextInt();
}

int countPositive = 0;

for (int i = 0; i < n; i++) {
    if (a[i] > 0) {
        countPositive++;
    }
}

System.out.println(countPositive);

Поиск элемента в массиве

int n = in.nextInt();
int[] a = new int[n];

for (int i = 0; i < n; i++) {
    a[i] = in.nextInt();
}

int key = in.nextInt();   // кого ищем
boolean found = false;

for (int i = 0; i < n; i++) {
    if (a[i] == key) {
        found = true;
        break;
    }
}

if (found) {
    System.out.println("YES");
} else {
    System.out.println("NO");
}

Что нужно запомнить

Одномерный массив — это набор значений одного типа, доступ к каждому по индексу:

int[] a = new int[n];

Индексы идут от 0 до a.length - 1, выход за границы массива приводит к ошибке.

Типичные шаблоны работы с массивом: чтение в цикле, проход по всем элементам, вычисление суммы, минимума/максимума, подсчёт количества элементов по условию.

Контейнер `vector`

В C++ существует специальный контейнер для хранения последовательности переменных одного типа данных. Такой контейнер называется vector.

Удобно представить себе vector как набор из n «коробочек», каждая может хранить переменную указанного типа данных. Все «коробочки» пронумерованы от 0 до n - 1.

Рассмотрим работу с вектором на примере задачи.

Задача: дана последовательность из n чисел. Выведите её в обратном порядке.

Решение:

#include <iostream>
#include <vector> // библиотека для работы с векторами
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v(n); // создаём вектор из n чисел
    for (int i = 0; i < n; ++i){
        cin >> v[i]; // считываем i-й элемент вектора
    }
    for (int i = n - 1; i >= 0; --i){ // цикл от n - 1 до 0
        cout << v[i] << " "; // выводим i-й элемент вектора
    }
    return 0;
}

Ввод

5
1 2 3 4 5

Вывод

5 4 3 2 1

Данную задачу можно решить иначе. Переставим элементы в векторе v так, чтобы они шли в обратном порядке.

Решение 2:

Поменяем v[0] с v[n - 1], v[1] с v[n - 2] и так далее до середины вектора.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i){
        cin >> v[i];
    }
    for (int i = 0; i < n / 2; ++i){
        int temp = v[i];
        v[i] = v[n - 1 - i];
        v[n - 1 - i] = temp;
    }
    for (int i = 0; i < n; ++i){
        cout << v[i] << " ";
    }
    return 0;
}

Методы `push_back` и `size()`

У вектора есть метод push_back, который добавляет элемент в конец вектора. Также у вектора есть метод size(), с помощью которого можно узнать его размер.

Рассмотрим применение этих методов на примере задачи.

Задача: дана последовательность из n чисел. Разделите её на две последовательности: в первой храните все неотрицательные числа из исходной последовательности, а во второй все отрицательные. Выведите полученные последовательности на экран, каждую на отдельной строке.

Решение:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> pos, neg; // создаём два пустых вектора pos и neg
    for (int i = 0; i < n; ++i)
    {
        int now;
        cin >> now; // считываем элементы исходной последовательности
        if (now >= 0){
            pos.push_back(now); // неотрицательное число добавляем в конец вектора pos
        } else {
            neg.push_back(now); // отрицательное число добавляем в конец вектора neg
        }
    }
    for (int i = 0; i < pos.size(); ++i){ // идём циклом по всем элементам вектора pos
        cout << pos[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < neg.size(); ++i){ // идём циклом по всем элементам вектора neg
        cout << neg[i] << " ";
    }
    return 0;
}

Поиск максимального и минимального элементов вектора

Задача: дана последовательность из n элементов. Поменяйте местами минимальный и максимальный элементы последовательности.

Решение:

Найдём индексы минимального и максимального элемента (imn и imx) и поменяем местами элементы последовательности с этими индексами.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i){
        cin >> v[i];
    }
    int imn = 0, imx = 0;
    for (int i = 0; i < n; ++i){
        if (v[i] < v[imn]){
            imn = i;
        }
        if (v[i] > v[imx]){
            imx = i;
        }
    }
    swap(v[imn], v[imx]); // меняем местами элементы с индексами imn и imx
    for (int i = 0; i < n; ++i){
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}

Заметим, что если бы мы меняли переменные v[imx] и v[imn] с помощью арифметических операций (без использования третьей переменной), то программа работала бы некорректно при imn == imx. В этом случае происходит обмен переменной с самой собой, и такой подход может дать неверный результат. Поэтому для обмена переменных нужно использовать функцию swap или алгоритм с дополнительной переменной.

Использование вектора для подсчёта чисел

Задача: в школе ученики получают оценки от 1 до 5. Дан список всех оценок одного ученика. Посчитайте, сколько оценок каждого вида он получил.

Решение:

Заведём вектор, в котором для каждой оценки будем хранить, сколько раз она встречалась в списке. Для упрощения кода вектор будет иметь 6 элементов, из которых будут использоваться только последние 5, так как оценки 0 не существует. Такой способ хранения не подходит, когда интервал значений находится далеко от 0, потому что тогда резервируется много неиспользуемой памяти.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> grades(6); // создаём вектор из 6 чисел, заполненный нулями
    for (int i = 0; i < n; ++i){
        int now;
        cin >> now;
        ++grades[now];
    }
    for (int i = 1; i <= 5; ++i){
        cout << i << " " << grades[i] << endl;
    }
    return 0;
}

Удаление повторов в векторе

Задача: дана последовательность из n чисел. Удалите повторяющиеся элементы: для каждого значения оставьте только первое его вхождение.

Например, для последовательности из 5 элементов 1, 2, 1, 2, 1 нужно оставить 1, 2.

Решение:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i){
        cin >> v[i];
    }
    for (int i = 0; i < n; ++i){
        bool flag = false;
        for (int j = 0; j < i; ++j){
            if (v[i] == v[j]){
                flag = true;
            }
        }
        if (!flag){
            cout << v[i] << " ";
        }
    }
    return 0;
}

Вопросы-ответы по видеолекции.

Добавление элемента в середину вектора

Задача: дан список из n целых чисел, число k и значение x. Необходимо вставить в список на позицию с индексом k элемент x, сдвинув все элементы с индексом не меньше k вправо.

Решение:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i){
        cin >> v[i];
    }
    int k, x;
    cin >> k >> x;
    v.push_back(0);
    ++n;
    for (int i = n - 1; i > k; --i){
        v[i] = v[i - 1];
    }
    v[k] = x;
    for (int i = 0; i < n; ++i){
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}

Вопросы-ответы по видеолекции.

Присваивание векторов

Задача: на математической олимпиаде было три задачи. По каждой задаче участник получает от 0 до 10 баллов. Победителем считается участник с максимальной суммой баллов. Дан протокол проверки (n строк по три числа). Выведите баллы победителя по каждой задаче. Гарантируется, что победитель единственный.

Решение:

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

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, maxsum = -1;
    vector<int> now(3), best(3);
    cin >> n;
    for (int i = 0; i < n; ++i){
        int nowsum = 0;
        for (int j = 0; j < 3; ++j){
            cin >> now[j];
            nowsum += now[j];
        }
        if (nowsum > maxsum){
            maxsum = nowsum;
            best = now;
        }
    }
    for (int i = 0; i < 3; ++i){
        cout << best[i] << " ";
    }
    return 0;
}

На примере этой задачи видно, что векторы можно присваивать друг другу. При присваивании одного вектора другому выполняется поэлементное копирование. Поэтому чем больше элементов копируемого вектора, тем дольше выполняется присваивание. При этом размеры векторов могут быть разными: операция всё равно отработает корректно.

По материалам:
М. Густокашин. Введение в программирование на языке C++. Сириус Курсы. Перейти к курсу.

В Python чаще всего используют список list.

n = 5
a = [0] * n   # n целых чисел: a[0], a[1], ..., a[n-1]

Основное

a = [0] * n   # создать массив длины n
a[i] = 10     # записать значение в ячейку i
x = a[i]      # прочитать значение
length = len(a)

Важно:

индексы идут от 0 до len(a) - 1;
при выходе за границы будет ошибка IndexError.

Чтение массива из ввода

Частый случай: сначала n, затем n чисел.

n = int(input())
a = list(map(int, input().split()))

for x in a:
    print(x)

Ввод

5
10 20 30 40 50

Вывод

Если числа могут прийти не в одной строке, проще читать все сразу:

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
a = data[1:1+n]

for x in a:
    print(x)

В Java массив — это отдельный тип (int[]), длина задаётся при создании и дальше не меняется. Длина берётся через a.length, выход за границы даёт ошибку во время работы.

В C++ для задач обычно используют std::vector. Его размер можно менять, длина берётся через a.size(). При выходе за границы через a[i] нет гарантированной ошибки: программа может работать неправильно или упасть позже.

В Python список list по смыслу ближе к vector: размер можно менять. Длина через len(a), выход за границы сразу даёт IndexError.

По умолчанию новые элементы равны нулю: Java new int[n], C++ vector<int> a(n), Python [0] * n.

Для чтения ввода обычно используют: Java — цикл и Scanner.nextInt(), C++ — цикл и cin >> a[i], Python — split() + map(int, ...) или чтение всего ввода через sys.stdin.read().

Массивы

Основное

Идея массива

Объявление и создание массива

Чтение массива из ввода

Примеры и типичные шаблоны

Что нужно запомнить

Контейнер vector

Методы push_back и size()

Поиск максимального и минимального элементов вектора

Использование вектора для подсчёта чисел

Удаление повторов в векторе

Добавление элемента в середину вектора

Присваивание векторов

Основное

Чтение массива из ввода

Контейнер `vector`

Методы `push_back` и `size()`