Задача
Даны два массива чисел. Требуется вывести те элементы первого массива (в том порядке, в каком они идут в первом массиве), которых нет во втором массиве.
Входные данные
Сначала подаётся количество [latex]n[/latex] элементов в первом массиве, затем [latex]n[/latex] чисел — элементы массива. Затем записано количество [latex]m[/latex] элементов во втором массиве. Далее заданы элементы второго массива. Количество элементов каждого массива не превышает [latex]100[/latex]. Все элементы — целые числа.
Выходные данные
В первой строке выведите количество искомых элементов, а во второй выведите те элементы первого массива, которых нет во втором, в том порядке, в каком они идут в первом массиве.
Тесты
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
| 1 | 7 3 1 3 4 2 4 12 6 4 15 43 1 15 1 |
4 3 3 2 12 |
| 2 | 5 12 16 17 45 68 6 1 93 45 68 34 38 |
3 12 16 17 |
| 3 | 10 15 47 68 59 75 25 35 61 21 86 10 15 47 69 58 75 26 36 61 21 89 |
5 68 59 25 35 86 |
| 4 | 10 15 47 68 59 75 25 35 61 21 86 10 15 47 68 59 75 25 35 61 21 86 |
0 0 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> using namespace std; int main() { bool q; int n, m, c = 0; int arr1[101], arr2[101], arr3[101]; cin >> n; for (int i = 0; i < n; i++) { cin >> arr1[i]; } cin >> m; for (int i = 0; i < m; i++) { cin >> arr2[i]; } for (int i = 0; i < n; i++) { q = false; for (int j = 0; j < m; j++) if (arr1[i] == arr2[j]) q = true; if (q == false) { arr3[c] = arr1[i]; c++; } } cout << c << endl; for (int i = 0; i < c - 1; i++) { cout << arr3[i] << " "; } cout << arr3[c - 1]; return 0; } |
Решение задачи
Для решения задачи нужно воспользоваться циклами, условными операторами и задать некий флаг, для проверки есть ли во втором массиве проверяемый элемент из первого. Пока идет проверка в это время считается и количество элементов первого массива, которых нет во втором. В конце выводим количество искомых элементов и их самих в том порядке, в котором они заданы в первом массиве.
Ваша программа работает за $O(n^2)$, что в принципе достаточно для ограничений задачи, но есть решение за $O(n \cdot log(n))$.
У Вас проблемы с табуляцией в коде.
Ну, хоть отступы поправьте.