1.2. “Массивы”

А.Шень “Программирование. Теоремы и задачи”

1.2.1 (Обнуление массива) 
Вариант 1:

1. int mas[max_size] = {0};

Вариант 2:

1. int mas[max_size];
2. memset(mas,0,sizeof(int) * max_size);

1.2.2 (Подсчет количества объектов) 

1. int mas[max_size];
2. . . .
3. int zeroesAmount = 0;
4. for (int i=0;i<max_size;i++)
5.   zeroesAmount += mas[i] == 0 ? 1 : 0;

1.2.3 (Копирование массивов) 

1. int a[max_size],b[max_size];
2. . . .
3. memcpy(b,a,max_size * sizeof(int));

1.2.4 (Максимальный элемент) 
Вариант 1:

1. int a[max_size];
2. int max_value = mas[0];
3. for (int i=1; i<max_size; i++)
4.   maxValue = max(max_Value,mas[i]);

Вариант 2: 

1. int mas[max_size];
2. . . .
3. int posMaxValue = 0;
4. for (int i=1; i<max_size; i++)
5.   posMaxValue = mas[i] > mas[posMaxValue] ? i : posMaxValue;

В общем случае второй вариант является более предпочтительным. Потому что он отвечает сразу на два вопроса.

1.2.5 (Количество различных элементов в неубывающем массиве) 

1. int mas[max_size];
2. . . .
3. int posMaxValue = 0;
4. for (int i=1; i<max_size; i++)
5.   posMaxValue = mas[i] > mas[posMaxValue] ? i : posMaxValue;

1.2.6 (см. 1.2.5 в произвольном массиве. Сложность O(N*N))
Сортировка выбором + 1.2.5

1.2.7 (см. 1.2.5 в произвольном массиве. Сложность О(N*logN)) 
Пирамидальная или Быстрая сортировка + 1.2.5

1.2.8 (см. 1.2.5 в произвольном массиве. Элементы массива в интервале [0,K]. Сложность O(N + K))
Сортировка подсчетом + 1.2.5

1.2.9 Количество прямоугольных единичных подматрицы
Решение

1.2.10 (Реверс массива)

1. void reverse(vector<int> &mas, int l, int r)
2. {
3.   while (l<r)
4.     swap(mas[l++],mas[r--]);
5. }

1.2.11 (Массив X = AB, где A и B – подмассивы. Реверснуть подмассивы и получить X = BA) 

Функция reverse из 1.2.10. m – индекс последнего элемента подмассива A.

1.   reverse(mas,0,m);
2.   reverse(mas,m+1,mas.size()-1);
3.   reverse(mas,0,mas.size()-1); 

1.2.12 (Схема Горнера)

1. int res = a[0];
2. for (int i=0;i<n-1;i++)
3.   res = res * x + a[i+1];

1.2.17 (Количество уникальных общих элементов в двух строго возрастающих массивах)

1. vector<int> a,b;
2. . . .
3. int commonAmount = 0;
4. int posA = 0, posB = 0;
5. while (posA < a.size() && posB < b.size())
6. {
7.   if (a[posA] == b[posB])
8.   {
9.     commonAmount++;
10.     posA++;
11.     posB++;
12.   }
13.   else if (a[posA] < b[posB])
14.     posA++;
15.   else
16.     posB++;
17. }

Данная задача имеет похожую природу, что и процедура слияния двух массивов в MergeSort

1.2.18 (Количество уникальных общих элементов в двух неубывающих массивах)

1. vector<int> a,b;
2. . . .
3. int commonAmount = 0;
4. int posA = 0, posB = 0;
5. while (posA < a.size() && posB < b.size())
6. {
7.   if (a[posA] < b[posB])
8.     posA++;
9.   else if (a[posA] > b[posB])
10.     posB++;
11.   else
12.   {
13.     posA++; posB++;
14.     while (posA < a.size() && a[posA] == a[posA-1])
15.       posA++;
16.     while (posB < b.size() && b[posB] == b[posB-1])
17.       posB++;
18.     commonAmount++;
19.   }
20. }

1.2.19 (Количество различных уникальных элементов в двух неубывающих массивах)
Решение  
1.2.20 (Объединить два упорядоченных массива в один)
Модификация функции merge в MergeSort 

1.2.21 (Пересечение двух неубывающих массивов)
Решение

1.2.22
1.2.23  
1.2.24
1.2.25
1.2.26
1.2.27
1.2.28
1.2.29
1.2.31
1.2.32
1.2.33 (Голландский флаг)
1.2.34
1.2.35
1.2.36