0

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

Если есть более оптимальный вариант решения данной задачи без использования 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)

1 ответ 1

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)
4
  • Ох. А ведь я реально не догадался. Спасибо большое. Успехов вам.
    – Иван
    22 окт 2020 в 9:09
  • Оборачивать в list излишне т.к сумма списков всегда будет списком.
    – AivanF.
    22 окт 2020 в 9:11
  • @AivanF, вы успели это заметить быстрее, чем я это исправил :) - действительно list избыточен
    – Zhihar
    22 окт 2020 в 9:15
  • @Иван, я там в ответе добавил еще один алгоритм, который исключает сортировку
    – Zhihar
    22 окт 2020 в 9:15

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.