LeetCode: проблема 23 - объединить отсортированные списки - PullRequest
Новая
       22

LeetCode: проблема 23 - объединить отсортированные списки

0 голосов
/ 07 мая 2019

Проблема , указанная в LeetCode, выглядит следующим образом:

Объединяет k отсортированных связанных списков и возвращает их как один отсортированный список.Проанализируйте и опишите его сложность.

Пример:

Ввод: [1-> 4-> 5, 1-> 3-> 4, 2-> 6] Выход: 1-> 1-> 2-> 3-> 4-> 4-> 5-> 6

Я могу пройти 129 из 131 тестовых случаев, но в случае 130 нажать «превышено ограничение по времени». Нижеэто моя реализация.

Может ли кто-нибудь определить узкое место?Любые предложения по улучшению сложности времени? 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # def print_lists(self, lists):
    #     idx = 0
    #     while idx < len(lists):
    #         ptr = lists[idx]
    #         _l = []
    #         while ptr is not None:
    #             _l.append(ptr.val)
    #             ptr = ptr.next
    #         idx += 1
    #         print(_l)

    def min_idx(self, lists):
        idx = 0

        for i in range(len(lists)):
            if lists[i] is None:
                continue
            elif lists[idx] is None:
                idx = i
            elif lists[i].val < lists[idx].val:
                idx = i
        return idx

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        head = tail = ListNode(-1)

        while len(lists) > 0:
            m_idx = self.min_idx(lists)

            if lists[m_idx] is None:
                return head.next

            tail.next = lists[m_idx]
            tail = tail.next
            lists[m_idx] = lists[m_idx].next

            if lists[m_idx] is None:
                del lists[m_idx]

        return head.next

Я столкнулся с проблемой "превышено ограничение по времени" в нашей без использования del.Контрольный пример 130 содержит 10 000 списков ссылок.

1 Ответ

1 голос
/ 07 мая 2019

Вот более простая и быстрая версия вашего кода, которая позволяет избежать нескольких ifs: 

def min_idx(self, lists):
    idx = 0

    for i in range(len(lists)):
        if lists[i].val < lists[idx].val:
            idx = i
    return idx

def mergeKLists(self, lists):
    head = tail = ListNode(-1)

    lists = list(filter(lambda x: x is not None, lists))

    while len(lists) > 0:
        m_idx = self.min_idx(lists)

        tail.next = lists[m_idx]
        tail = tail.next
        lists[m_idx] = lists[m_idx].next

        if lists[m_idx] is None:
            del lists[m_idx]

    return head.next

Для еще лучшего времени вам нужно изменить реализацию на:

  • Использование кучи для уменьшения операции min_idx до O (log k) вместо O (k), равного k количеству списков
  • Просто выбросить все в один массив, отсортировать его и поместить обратно в ListNode
  • Произвести слияние двух списков в O (длина самого длинного списка) и рекурсивно объединить в пары, пока не останется 1
...