← Назад к вопросам
Общие элементы двух массивов
2.0 Middle🔥 161 комментариев
#Теория тестирования
Условие
Напишите метод, который проверяет, есть ли в двух массивах одинаковые элементы, и возвращает их.
Пример
Вход: [1, 2, 3, 4], [3, 4, 5, 6] Выход: [3, 4]
Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Решение: Общие элементы двух массивов
Описание задачи
Требуется реализовать метод для поиска пересечения двух массивов (intersection of arrays). Необходимо найти все элементы, которые присутствуют в обоих массивах одновременно, и вернуть их. Эта задача часто встречается в тестировании обработки коллекций данных, сравнении наборов данных, анализе пересечений и работе с множествами. Решение требует выбора оптимального алгоритма в зависимости от размера массивов и наличия дубликатов.
Решение на Python
def find_common_elements(arr1, arr2):
"""
Найдёт общие элементы двух массивов.
Args:
arr1: первый массив целых чисел
arr2: второй массив целых чисел
Returns:
список общих элементов (без дубликатов, в порядке первого массива)
"""
# Преобразуем второй массив в множество для O(1) поиска
set_arr2 = set(arr2)
# Сохраняем порядок первого массива
result = []
seen = set()
for element in arr1:
# Если элемент есть во втором массиве и мы его ещё не добавили
if element in set_arr2 and element not in seen:
result.append(element)
seen.add(element)
return result
Альтернативные подходы
1. Использование пересечения множеств
def find_common_elements_set(arr1, arr2):
"""
Самый просто и Pythonic способ — использовать операции над множествами.
Возвращает результат в произвольном порядке.
"""
common = set(arr1) & set(arr2)
return list(common)
2. С сохранением порядка
def find_common_elements_ordered(arr1, arr2):
"""
Сохраняет порядок элементов из первого массива.
"""
set_arr2 = set(arr2)
return [x for x in arr1 if x in set_arr2]
3. Двойной цикл (наивный подход)
def find_common_elements_brute_force(arr1, arr2):
"""
Наивный подход с двойным циклом.
O(n*m) временная сложность — неэффективно!
"""
result = []
for x in arr1:
for y in arr2:
if x == y and x not in result:
result.append(x)
break
return result
4. С использованием sorted массивов
def find_common_elements_sorted(arr1, arr2):
"""
Использует сортировку и двухуказательный подход.
Хорош если массивы уже отсортированы.
"""
arr1_sorted = sorted(arr1)
arr2_sorted = sorted(arr2)
result = []
i, j = 0, 0
while i < len(arr1_sorted) and j < len(arr2_sorted):
if arr1_sorted[i] == arr2_sorted[j]:
# Добавляем только если это не последнее добавленное значение
if not result or result[-1] != arr1_sorted[i]:
result.append(arr1_sorted[i])
i += 1
j += 1
elif arr1_sorted[i] < arr2_sorted[j]:
i += 1
else:
j += 1
return result
5. С использованием Counter (для подсчёта повторений)
from collections import Counter
def find_common_elements_count(arr1, arr2):
"""
Использует Counter для сохранения информации о частоте элементов.
Полезно если нужно знать количество пересечений.
"""
counter1 = Counter(arr1)
counter2 = Counter(arr2)
result = []
for element in counter1:
if element in counter2:
# Добавляем столько раз, сколько элемент есть в обоих массивах
for _ in range(min(counter1[element], counter2[element])):
result.append(element)
return result
6. С использованием filter
def find_common_elements_filter(arr1, arr2):
"""
Функциональный подход с filter.
"""
set_arr2 = set(arr2)
seen = set()
def is_common_and_new(x):
if x in set_arr2 and x not in seen:
seen.add(x)
return True
return False
return list(filter(is_common_and_new, arr1))
Тестовые примеры
import unittest
class TestFindCommonElements(unittest.TestCase):
def test_basic_case(self):
# Базовый случай из условия
assert find_common_elements([1, 2, 3, 4], [3, 4, 5, 6]) == [3, 4]
def test_no_common_elements(self):
# Нет общих элементов
assert find_common_elements([1, 2, 3], [4, 5, 6]) == []
def test_all_common(self):
# Все элементы общие
assert find_common_elements([1, 2, 3], [1, 2, 3]) == [1, 2, 3]
def test_empty_arrays(self):
# Пустые массивы
assert find_common_elements([], []) == []
assert find_common_elements([1, 2], []) == []
assert find_common_elements([], [1, 2]) == []
def test_single_element(self):
# Один элемент
assert find_common_elements([1], [1]) == [1]
assert find_common_elements([1], [2]) == []
def test_duplicates_in_first(self):
# Дубликаты в первом массиве
result = find_common_elements([1, 1, 2, 2, 3], [2, 3, 4])
assert result == [2, 3]
def test_duplicates_in_second(self):
# Дубликаты во втором массиве
result = find_common_elements([1, 2, 3], [2, 2, 3, 3, 4])
assert result == [2, 3]
def test_order_preserved(self):
# Порядок элементов из первого массива сохранён
result = find_common_elements([5, 3, 1, 4, 2], [2, 3, 4, 5])
assert result == [5, 3, 4, 2]
def test_negative_numbers(self):
# С отрицательными числами
assert find_common_elements([-1, 0, 1], [-1, 2, 3]) == [-1]
def test_large_arrays(self):
# Большие массивы
arr1 = list(range(0, 100, 2)) # Чётные: 0, 2, 4, ..., 98
arr2 = list(range(0, 100, 3)) # Кратные 3: 0, 3, 6, ..., 99
# Общие: 0, 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96
result = find_common_elements(arr1, arr2)
expected = [i for i in arr1 if i in arr2]
assert result == expected
def test_multiple_duplicates(self):
# Несколько дубликатов в обоих
result = find_common_elements([1, 1, 2, 2, 3], [1, 2, 2, 3, 3])
# Каждый общий элемент должен быть в результате один раз
assert set(result) == {1, 2, 3}
assert len(result) == 3
Анализ сложности
| Подход | Временная сложность | Пространственная сложность | Примечание |
|---|---|---|---|
| С множеством | O(n + m) | O(m) | Рекомендуется |
| Пересечение множеств | O(n + m) | O(min(n,m)) | Простой код, нет порядка |
| Двойной цикл | O(n * m) | O(1) | Очень медленно |
| Сортировка + двухуказатель | O(n log n + m log m) | O(1) | Если уже отсортировано |
| Counter | O(n + m) | O(n + m) | Если нужны дубликаты |
Применение в QA Automation
- Сравнение наборов данных — проверка, что два набора имеют одинаковые элементы
- Проверка пересечений — убедиться, что две коллекции имеют общие элементы
- Тестирование операций с множествами — проверка алгоритмов работы с множествами
- Граничные случаи — пустые массивы, нет пересечений, полное совпадение
- Генерация тестовых данных — автоматическое создание массивов с определённым пересечением
Выбор подхода
- Нужна простота: используйте пересечение множеств
set(arr1) & set(arr2) - Важен порядок: используйте подход с множеством и сохранением порядка
- Большие массивы: используйте подход с множеством (O(n+m))
- Уже отсортировано: используйте двухуказательный подход
- Нужны дубликаты: используйте Counter
Рекомендация
Для стандартного использования в QA рекомендуется подход с множеством и сохранением порядка — он обеспечивает хороший баланс между скоростью O(n+m) и функциональностью. Для быстрого кода в REPL используйте пересечение множеств. Двойной цикл использовать только если массивы очень маленькие или в образовательных целях.