Два масива
(https://www.e-olymp.com/uk/problems/2099)
Умова:
Задано два масиви чисел. Потрібно вивести ті елементи першого масиву (у том ж порядку, у якому вони йдуть у першому масиві), яких немає у другому масиві.
Вхідні дані:
Спочатку на вхід подається кількість елементів n у першому масиві, потім n чисел - елементи масиву. Далі записано кількість елементів m у другому масиві. Потім записано елементи другого масиву. Кількість елементів кожного масиву не перевищує 100. Усі елементи - цілі числа.
Вихідні дані:
У першому рядку виведіть кількість шуканих елементів, а у другому виведіть ті елементи першого масиву, яких немає у другому, у том у ж порядку, у якому вони йдуть у першому масиві.
Ліміт часу: 1 секунда
Ліміт використання пам'яті: 128 MiB
Джерело: Китеня 2011 м.Ковров
Приклад вхідних даних:
7
3 1 3 4 2 4 12
6
4 15 43 1 15 1
Приклад вихідних даних:
4
3 3 2 12
Задача нескладна, має на сайті e-olymp.com рейтинг cкладності всього 8%.
Проте під час розв’язку варто звернути увагу на одну цікаву особливість роботи зі списками.
Для початку пропоную створити третій список, в який будемо накопичувати значення елементів першого списку, що відповідають умові задачі. Наприклад:
input()
first = [int(x) for x in input().split()]
input()
second = [int(x) for x in input().split()]
third = []
for x in first:
if x not in second:
third.append(x)
print(len(third))
print(' '.join(map(str, third)))
Хоча для оптимального розв’язку буде логічним мінімальне використання пам’яті, тому спробуємо розв’язати дану задачу без додаткового списку. Наприклад:
Перебрати всі елементи першого списку. Якщо елемент з таким значенням є в другому списку, то видалити цей елемент з першого списку. Після перебору кожного елементу першого списку таким способом, у ньому залишаться тільки такі елементи, яких немає в другому списку, що нам і потрібно.
Приклад коду:
input()
first = [int(x) for x in input().split()]
input()
second = [int(x) for x in input().split()]
for x in first:
if x in second:
first.remove(x)
print(len(first))
print(' '.join(map(str, first)))
Це виглядає значно оптимальніше, програма відпрацьовує тестовий приклад, але не проходить всі тести на сайті e-olymp.com Що ж не так?
Справа в тому, що ми змінюємо список, який перебираємо. І отримуємо проблему.
Поясню на прикладі.
Нехай наш перший список: [1,2,3,4,5]
Другий список: [2,3]
Який ми повинні отримати результат? [1,4,5].
Але програма видає [1,3,4,5].
Звідки взялася трійка, програма ж повинна була її видалити!
Ось тут і є особливість. Як цикл for буде перебирати числа? По черзі. Перший елемент, другий елемент, третій елемент і т.д.
А тепер давайте послідовно проаналізуємо значення елементів першого списку: [1,2,3,4,5]
Перший елемент – одиниця, якої немає в другому списку. Отже, одиниця – унікальна, ми її не чіпаємо.
Другий елемент в прикладі – двійка. Вона є в другому списку. Тому ми її видаляємо.
Який список залишається? [1,3,4,5]. Отже, який елемент списку ми відпрацювали? Другий?
Правильно. Беремо третій. Це четвірка. А чому четвірка?
А тому що при видаленні двійки, всі елементи зсунулися і місце видаленої двійки зайняла трійка. Саме трійка стала другим елементом після видалення двійки.
Але цикл, який вже відпрацював другий елемент при наступній ітерації бере собі в роботу третій елемент, таким чином пропускаючи трійку. Виходить, наш підхід неправильний.
Аналізуючи даний приклад можна зробити очевидний висновок: якщо циклом перебираються елементи списку, то змінювати кількість елементів цього списку в циклі треба обережно, бо видалення або додавання елементів може стати причиною неправильного розв'язку.
Цю задачу, звичайно, можна розв'язати без використання третього списку. Але треба враховувати, що при видаленні, наприклад, другого елемента, список змінюється і далі потрібно знову аналізувати другий елемент. Наприклад:
count = int(input())
first = [int(x) for x in input().split()]
input()
second = [int(x) for x in input().split()]
x = 0
while count > x:
if first[x] in second:
first.remove(first[x])
count -= 1
else:
x += 1
print(len(first))
print(' '.join(map(str, first)))
Який шлях краще обрати для розв’язку? Якщо у програміста цейтнот і немає обмежень по пам’яті, то, можливо, варто скористатися простим і логічним варіантом з третім списком. А якщо ви прийшли на співбесіду щодо працевлаштування, то, мабуть… також. Як це не дивно. Але ж ми ж використовуємо менше пам’яті! Це правда, але давайте уважно перечитаємо умову: «Потрібно вивести ті елементи першого масиву…». Хто ж нам дозволяв змінювати цей масив? :)