Как объединить два отсортированных массива в Python?

Question

Как я могу объединить два отсортированных массива в один? Мой код, направленный на решение данной задачи не работает.

Если есть более оптимальный вариант решения данной задачи без использования heapq, это тоже считается ответом на мой вопрос.

# Функция для объединения двух отсортированных массивов
from heapq import merge
def mergeArray(arr1,arr2):
    return list(merge(arr1, arr2))

  
# Функция драйвера
if __name__ == "__main__":

    arr1 = [1,3,4,5]  

    arr2 = [2,4,6,8]

    print mergeArray(arr1, arr2)

Answer 1

решение в лоб уже не устраивает?

arr1 = [1,3,4,5]  

arr2 = [2,4,6,8]

print(sorted(arr1 + arr2))

оно конечно не такое быстрое, как можно сделать специализированное, но очень дешевое и сердитое (в смысле короткое и понятное) :)

Но чтобы не делать лишнюю сортировку можно обойтись алгоритмом со сложностью O(n):

res = []

i, j = 0, 0
while i < len(arr1) or j < len(arr2):
    if i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            res.append(arr1[i])
            i += 1
        else:
            res.append(arr2[j])
            j += 1
    elif i < len(arr1):
        res.append(arr1[i])
        i += 1
    else:
        res.append(arr2[j])
        j += 1

print(res)

БЛОГ НА HUSL

Как объединить два отсортированных массива в Python?

Ответы (1 шт):