2099. Два массива

Даны два массива чисел. Выведите те элементы первого массива (в том порядке, в каком они идут в первом массиве), которых нет во втором массиве.

Вход. Сначала подаётся количество n элементов в первом массиве, затем n чисел – элементы массива. Затем записано количество m элементов во втором массиве. Далее заданы элементы второго массива. Количество элементов каждого массива не превышает 100. Все элементы – целые числа.

Выход. В первой строке выведите количество искомых элементов, а во второй выведите те элементы первого массива, которых нет во втором, в том порядке, в каком они идут в первом массиве.

Пример входа	Пример выхода
7 3 1 3 4 2 4 12 6 4 15 43 1 15 1	4 3 3 2 12

РЕШЕНИЕ

структура данных – set

Анализ алгоритма

Занесем элементы первого массива в линейный массив, а элементы второго массива во множество set. Совершим следующие операции:

· Подсчитаем количество элементов первого массива, которых нет во множестве (втором массиве).

· Выведем это количество.

· Еще раз пройдем по элементам первого массива и выведем те из них, которых нет во множестве (втором массиве).

Пример

Слева приведен первый массив. Справа – множество, в которое поместили все элементы второго массива. Выделены элементы первого массива, которых нет во множестве (втором массиве).

Реализация алгоритма

Читаем входные данные.

scanf("%d",&n);

for(i = 0; i < n; i++)

scanf("%d",&mas[i]);

scanf("%d",&m);

Заносим элементы второго массива во множество s.

for(i = 0; i < m; i++)

{

scanf("%d",&val);

s.insert(val);

}

В переменной cnt подсчитываем количество элементов первого массива, которых нет во втором.

cnt = 0;

for(i = 0; i < n; i++)

if (s.find(mas[i]) == s.end()) cnt++;

Выводим количество искомых элементов.

printf("%d\n",cnt);

Выводим элементы первого массива, которых нет во втором.

for(i = 0; i < n; i++)

if (s.find(mas[i]) == s.end()) printf("%d ",mas[i]);

printf("\n");

Java реализация

import java.util.*;

//import java.io.*;

public class Main

{

public static void main(String []args) //throws IOException

{

Scanner con = new Scanner(System.in);

//Scanner con = new Scanner(new FileReader ("2099.in"));

TreeSet<Integer> s = new TreeSet<Integer>();

int n = con.nextInt();

int mas[] = new int[n];

for(int i = 0; i < n; i++)

mas[i] = con.nextInt();

int m = con.nextInt();

for(int i = 0; i < m; i++)

{

int val = con.nextInt();

s.add(val);

}

int cnt = 0;

for(int i = 0; i < n; i++)

if (!s.contains(mas[i])) cnt++;

System.out.println(cnt);

for(int i = 0; i < n; i++)

if (!s.contains(mas[i])) System.out.print(mas[i] + " ");

con.close();

}

}