Re: [閒聊] leetcode 大師請進已回收

看板Marginalman作者 (動物園 公告)時間1年前 (2024/05/06 23:46), 1年前編輯推噓2(2推 0噓 9→)
留言11則, 4人參與, 1年前最新討論串5/8 (看更多)
這題不可能 O(N^2) 啦 最差就是快速排序 然後從最後面插元素回第一個 O(nlogn) 但是應該有更好的方法 我一直想不到 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.227.135 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715010405.A.D72.html 有沒有可能先找一個不動的最大子序列 然後把剩下的在找最大子序列 依序下去 直到所有元素都被找完 然後反向插回去 有沒有搞頭 還沒細想可不可行 ※ 編輯: ZooseWu (114.32.227.135 臺灣), 05/06/2024 23:51:00
→
05/06 23:50, 1年前 , 1F
10^3 N^2 leetcode應該會爆掉吧
05/06 23:50, 1F
→
05/06 23:50, 1年前 , 2F
NlogN夠好了
05/06 23:50, 2F
推
05/06 23:51, 1年前 , 3F
不太可能降到n吧
05/06 23:51, 3F
插入的成本很大 所以我覺得先找最大子序列 剩下的元素快速排序 然後依序插進去原本序列這樣 這個成果我已經能接受了 ※ 編輯: ZooseWu (114.32.227.135 臺灣), 05/06/2024 23:52:59
→
05/06 23:52, 1年前 , 4F
只是要排序用計數排序就可以壓了 都正整數
05/06 23:52, 4F
→
05/06 23:52, 1年前 , 5F
這題擊敗的地方是要記索引==
05/06 23:52, 5F
→
05/06 23:53, 1年前 , 6F
沒有上限一樣可以計數排序嗎？這樣會變空間成本很大吧
05/06 23:53, 6F
→
05/06 23:56, 1年前 , 7F
喔沒事 你說三位數是測資大小 你只是說正整數沒說上限
05/06 23:56, 7F
→
05/06 23:58, 1年前 , 8F
限制就是正整數 XD
05/06 23:58, 8F
推
05/07 00:01, 1年前 , 9F
我哭了 這題好難 只剩我解不出來還想錯了
05/07 00:01, 9F
→
05/07 00:02, 1年前 , 10F
我以為是 mid 的難度 只是我太久沒寫leetcode才想不出來
05/07 00:02, 10F
→
05/07 00:02, 1年前 , 11F
沒想到看起來是 hard
05/07 00:02, 11F
‣ 更多 ZooseWu 的文章
文章代碼(AID): #1cEFjbro (Marginalman)
討論串 (同標題文章)
完整討論串 (本文為第 5 之 8 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共8篇)
‣ 更多 ZooseWu 的文章
文章代碼(AID): #1cEFjbro (Marginalman)