Условие

Есть два сортированных списка (массива).

Нужно написать функцию, которая делает новый сортированный список с объединением.

1-ый список: 1, 2, 2, 5, 7, 14

2-ий список: 2, 2, 2, 4, 6, 6, 7, 9, 14, 15

answer: 1, 2, 2, 2, 4, 5, 6, 6, 7, 9, 14, 15

def union(arr1: list[int], arr2: list[int]) -> list[int]: pass

def union(arr1: list[int], arr2: list[int]) -> list[int]: result = [] i = 0 j = 0

while i < len(arr1) and j < len(arr2):
    if arr1[i] < arr2[j]:
        result.append(arr1[i])
        i += 1
    elif arr1[i] > arr2[j]:
        result.append(arr2[j])
        j += 1
    else:
        result.append(arr1[i])
        result.append(arr2[j])
        i += 1
        j += 1
result.extend(arr1[i:])
result.extend(arr2[j:])

return result

Ответ

По ожидаемому ответу требуется объединение мультимножеств: число повторов равно максимуму из двух списков, а не сумме. При равных элементах нужно добавить один и сдвинуть оба указателя.

def union(arr1, arr2):
    result = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            result.append(arr1[i]); i += 1
        elif arr1[i] > arr2[j]:
            result.append(arr2[j]); j += 1
        else:
            result.append(arr1[i]); i += 1; j += 1
    result.extend(arr1[i:])
    result.extend(arr2[j:])
    return result

Именно двойной append в исходном else даёт лишние повторы. Время O(n + m), память результата O(n + m). Обычное слияние с суммой повторов тоже возможно, но не соответствует приведённому answer.