0

Нужна критика метода решения и подсказка по вопросу (даже если способ решения логически неверен, сам вопрос остается актуальным для понимания питона как такового). Решаю задачу на сортировку. Есть N сортированных списков чисел, они объединяются в новый отсортированный список. Естественно, метод sort() использовать нельзя)) На степике была задача с двумя списками (и описание метода решения), но теперь число списков произвольное. Вначале я пытался приспособить метод объединения двух списков к ситуации, когда число списков равно N. Но потом отказался от этой идеи, т.к. решил что тут не поможет простая экстраполяция, да и пришла другая идея решения. Допустим, у нас есть список из трех списков:

[[1, 2, 3, 7, 12]
 [4, 6, 45, 655]
 [23, 56, 789]]

Тут даже не надо учитывать тот факт, что у вложенных списков может быть разная длина. Делаю цикл, в котором сравниваю элементы столбца имеющие индекс i[0] и минимальное число в столбце добавляю в пустой результирующий список. После этого удаляю это минимальное число из первого списка и повторяю поиск, в результате чего первый "список списков" становится пустым, а результирующий наполняется элементами в порядке возрастания. Но возникает ошибка при попытке найти минимум из элементов столбца:

for i in range(a):
    print(min(i[0]))

TypeError: 'int' object is not subscriptable

Ошибка получается и если сделать через i-j:

for i in range(a):
    for j in i:
        print(min(i[0]))

При этом если я вывожу элементы первого столбца:

for i in bl:
    print(i[0], end=' ')

то благополучно получаю 1, 4, 23. Но я ведь перебираю первые элементы вложенных списков, а не пытаюсь перебрать сам элемент, на что мне указывает питон. В интернете не нашел разбора задач на нахождение минимального (либо максимального) элемента столбца двумерного списка. Но ведь это должно как-то решаться, задача по идее нередкая. Что думаете по поводу самого метода решения? (помня что по условия метод sort не используем). Спасибо!

Кусок кода с вводом числа списков и проверкой вывода:

a = int(input())
result = []
bl = []
for i in range(a):
    bl.append(list(map(int, input().split())))

print('\n'.join(map(str, bl)))

for i in bl:
    print(i[0], end=' ')   # вывожу элементы первого столбца  

for i in range(a):
    print(min(i[0]))  # ищу минимум в первом столбце (и получаю сообщ. об ошибке)

1 ответ 1

0

Идея подхода у вас верная, реализация подкачала.

В общем, слияние К сортированных списков наиболее выгодно осуществлять с помощью структуры данных "Очередь по приоритетам", обычно она делается на основе бинарной кучи (binary heap).

Возможная реализация:

  • в кучу складывается К пар - (индекс в списке; номер списка). Можно сделать триплет, первым элементом ещё добавить значение соответствующего элемента.
  • на каждом шаге снимается вершина кучи - самый маленький из текущих элементов, его значение идёт на выход, индекс соответствующего списка увеличивается, если он не вышел за пределы - то триплет с обновленным значением и индексом снова кладется в кучу
  • повторяется до исчерпания кучи

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

В Python есть стандартный модуль heapq, с его помощью легко организовать кучу над списком (триплетов или пар). Создали список туплей М, затем heapq.heapify(М) на каждом шаге с=heapq.heappop(М), heapq.heappush(М, new_c)

1
  • Спасибо за ответ. Почитал немного по теме, просмотрел пару роликов на ютубе. Пока моих знаний недостаточно чтобы это реализовать на уровне кода, хотя суть вроде бы понял.
    – Alex53
    Commented 11 дек. 2022 в 23:13

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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