PTT數位生活區 / Python

[問題] LC 505 the maze ii

看板Python作者 (.)時間6年前 (2019/01/13 09:49), 編輯推噓1(1推 0噓 3→)
留言4則, 1人參與, 6年前最新討論串1/1
Leetcode 505. The Maze II 時間複雜度怎麼計算? 這題鎖上了。題目請見這篇：http://www.cnblogs.com/grandyang/p/6725380.html https://paste.ubuntu.com/p/6rDhmhGsks/ 用min heap 代替 queue實現最短路徑 但是我不會估算時間複雜度 請大家解惑 我最早的想法：總共m*n個點，heap裡面最多就是m*n個點， 所以每次彈出的複雜度就是log(m*n) 總共m*n個點，所以是m*n*log(m*n) 每次彈出之後有滾動， 那麼就變成 m*n*log(m*n)*max(m,n) leetcode solution 解答上寫此方法的時間複雜度為 m*n*log(m*n) 那麼每一個點彈出之後的滾動呢？ 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.189.14.17 ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1547344143.A.7D1.html
推
01/13 11:13, 6年前 , 1F
你那樣想不是最小的upper bound
01/13 11:13, 1F
→
01/13 11:13, 6年前 , 2F
注意到每一個node不會再被塞進heap
01/13 11:13, 2F
→
01/13 11:13, 6年前 , 3F
而且每次只更新上下左右四個點
01/13 11:13, 3F
→
01/13 11:13, 6年前 , 4F
這是Dijkstra alg的精髓
01/13 11:13, 4F
‣ 更多 sean72 的文章
文章代碼(AID): #1SEfaFVH (Python)
Python 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 sean72 的文章
文章代碼(AID): #1SEfaFVH (Python)