Минимальный элемент в столбце двумерного массива. Питон

Question

Нужна критика метода решения и подсказка по вопросу (даже если способ решения логически неверен, сам вопрос остается актуальным для понимания питона как такового). Решаю задачу на сортировку. Есть 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]))  # ищу минимум в первом столбце (и получаю сообщ. об ошибке)

Answer 1

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

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

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

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

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

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

Answer 2

В вопросе упоминалась функция merge(list1, list2), которая "смешивает" два упорядоченных списка в один упорядоченный список. Её можно применит к задаче, когда у вас списков больше чем два. Только это надо делать с головой.

Последовательное подмешивание списков к общему результату приведёт к медленному решению. Код ниже имеет квадратичную сложность относительно количества списков. Лучший способ это проверить – скормить ему много списков из одного элемента, тогда этот код будет работать как сортировка вставками.

def merge_multy(lists):
    result = []
    for list_ in lists:
        result = merge(result, list_)
    return result

Значительно быстрее будет разбить списки на пары, смешать каждую пару в отдельности, поместить результаты в новый список, который окажется примерно в два раза короче исходного. Процесс повторяется пока не останется только один список. На наборе одноэлементных списков этот код работает как сортировка слиянием, со сложностью n log n.

def merge_multy(lists):
    if len(lists) == 0:
        return []
    while len(lists) > 1:
        new_lists = []
        for i in range(0, len(lists), 2):
            if i == len(lists) - 1:
                new_lists.append(lists[i])
            else:
                new_lists.append(merge(lists[i], lists[i + 1]))
        lists = new_lists
    return lists[0]

БЛОГ НА HUSL

Минимальный элемент в столбце двумерного массива. Питон

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