關於 web service, unity, blogger 等軟體工程筆記

LeetCode #23 Merge k Sorted Lists

Edit icon 沒有留言
LeetCode using Golang
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

在這次問題中,嘗試使用 Go 來實作三種不同的解題方式,總結其複雜度分析如下,假設有 k sorted lists,且共有 N 資料元素 (數值):

實作解法 空間複雜度 時間複雜度
暴力排序法 O(N) O(NlogN)
尋找最小值 O(1) O(Nk)
使用 Priority queue O(k) O(Nlogk)

分析與解法 - 暴力排序法

最直觀且直覺的想法,是列舉所有資料元素,把所有的數值塞到一個陣列中,然後執行排序演算法後,再輸出結果。

且 Go 標準函式庫已經有實作排序 sort,直接拿來使用就可以了

/**
* Definition for singly-linked list.
* type ListNode struct {
*    Val int
*    Next *ListNode
* }
*/
import(
   "sort"
)

type nodeSorter struct {
   vals []*ListNode
}

func (ns nodeSorter) Len() int {
   return len(ns.vals)
}

func (ns nodeSorter) Less(i, j int) bool {
   return ns.vals[i].Val < ns.vals[j].Val
}

func (ns *nodeSorter) Swap(i, j int) {
    t := ns.vals[i]
    ns.vals[i] = ns.vals[j]
    ns.vals[j] = t
}

func mergeKLists(lists []*ListNode) *ListNode {
   vals := make([]*ListNode, 0)
   for _, list := range lists {
      for itr := list; itr != nil; itr = itr.Next {
         vals = append(vals, itr)
      }
   }
   if len(vals) <= 0 {
      return nil
   }
   sort.Sort(&nodeSorter{vals})
   for i := 1; i < len(vals); i++ {
      vals[i-1].Next = vals[i]
   }
   vals[len(vals)-1].Next = nil
   return vals[0]
}

假設 k lists 中,共有 N 個資料元素,計算此演算法複雜度:

  • 空間複雜度:O(N)
    • 需要將所有資料塞入到陣列中排序
  • 時間複雜度: O(NlogN)
    • 列舉將所有資料元素,並塞入到陣列 O(N)
    • Go 排序是採用 Quick Sort,取一般情況 O(NlogN)

分析與解法 - 尋找最小值

考慮已知條件,k 個 lists 本身內資料元素已經有排序,因此可以考慮每次從 k lists 挑出最小的數值,直到每一個 list 都沒有元素,最後完成輸出。

演算法示意圖,每次都從 lists 中挑出最小的數值

演算法示意圖,每次都從 lists 中挑出最小的數值

/**
* Definition for singly-linked list.
* type ListNode struct {
*    Val int
*    Next *ListNode
* }
*/

func mergeKLists(lists []*ListNode) *ListNode {
   var head, itr *ListNode
   for true {
      // Find smallest
      sidx := -1
      for i := 0; i < len(lists); i++ {
         comparer := lists[i]
         if comparer != nil {
            if sidx < 0 || comparer.Val < lists[sidx].Val {
               sidx = i
            }
         }
      }
      if sidx < 0 {
         break
      } else {
         if itr == nil {
            head = lists[sidx]
            itr = head
         } else {
            itr.Next = lists[sidx]
            itr = itr.Next
         }
         lists[sidx] = lists[sidx].Next
      }
   }
   if itr != nil {
      itr.Next = nil
   }
   return head
}

假設 k lists 中,共有 N 個資料元素,計算此演算法複雜度:

  • 空間複雜度:O(1)
    • 不需要額外配置資料陣列 (allocate array)
  • 時間複雜度:O(Nk)
    • 列舉所有資料元素 O(N)
    • 每次從 k lists 中挑出最小的資料 O(k)

分析與解法 - 使用 Priority queue

這算是上一個演算法的改良吧,自己並沒有在第一時間想到,而是完成以上兩種演算法實作後,搜尋別人解法而理解到,也順帶複習以前沒有學好的資料結構,搞懂什麼是 heap 啊。

上述演算法從 k lists 中,挑出最小資料元素的複雜度是 O(k),但如果採用 heap 資料結構,確保每次可以拿到最小的資料 (min-heap),若該 heap 只有 k 元素,每次插入新元素複雜度只要 O(k),取得並移除最小值元素的複雜度也是為 O(k)。

Pop 操作示意圖

Pop 操作示意圖

Push 操作示意圖

Push 操作示意圖

幸好,Go 標準函式庫中也有 heap 的實作,所以寫起來還算是輕鬆。

/**
* Definition for singly-linked list.
* type ListNode struct {
*    Val int
*    Next *ListNode
* }
*/

type PriorityQueue []*ListNode
func (pq PriorityQueue) Len() int {
   return len(pq)
}
func (pq PriorityQueue) Less(i, j int) bool {
   return pq[i].Val < pq[j].Val
}
func (pq PriorityQueue) Swap(i, j int) {
   // Swap, Go syntactic sugar
   pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
   item := x.(*ListNode)
   *pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
   old := *pq
   n := len(old)
   item := old[n-1]
   *pq = old[0 : n-1]
   return item
}
func mergeKLists(lists []*ListNode) *ListNode {
   pq := make(PriorityQueue, 0, len(lists))
   for _, v := range lists {
      if v != nil {
         pq = append(pq, v)
      }
   }
   heap.Init(&pq)
   var head, itr *ListNode
   for pq.Len() > 0 {
      ele := heap.Pop(&pq).(*ListNode)
      if ele.Next != nil {
         heap.Push(&pq, ele.Next)
         ele.Next = nil
      }
      if itr == nil {
         head = ele
         itr = ele
      } else {
         itr.Next = ele
         itr = itr.Next
      }
   }
   return head
}

假設 k lists 中,共有 N 個資料元素,計算此演算法複雜度:

  • 空間複雜度:O(k)
    • heap 空間配置
  • 時間複雜度:O(Nlogk)
    • 列舉所有資料元素 O(N)
    • 每次插入資料元素到 heap 中 O(k)
    • 每次從 heap 讀取最小值 (Pop) O(1)

沒有留言: