[LeetCode] Permutation Sequence

算是有點延續上周還是這周寫的

畢竟題目蠻相似的,換句話說就是…

不用動腦啊啊啊

修一修就submit了,結果….Time Limit Exceeded QQ

不過好像也是,我只是想知道其中一個branch,好像沒必要走不必要的path

原本這個tree上,我應該只要知道每次要走第幾個分支就好了

拿(4,9)這個input做例子

4!總共有24個組合,1到4開頭的會各有6(3!)個,聽起來很像廢話

但就是這個廢話(真的是很多廢話),好了不說廢話了XD

 

把剛剛我們要找9的去除以6

9/6 = 1….3

所以代表我從root出發要走的分支是第二個分支”2″,然後並把2從array pop掉

這時候數字array剩三個數字(1,3,4) ,每個數字開頭分別是2(2!)個

再重複剛剛的作法

3 / 2 = 1…1

一樣還是第二個分支”3″,然後並2 pop掉

重複這樣的步驟直到原先的array被抽光

“2314”就是答案惹

看討論區最熱門的solution也是這個解法,但這應該是O(N^2)吧

list pop就是O(N)的時間,討論區是用Java array要remove也是O(N)

 

BTW,不小心更新到主題惹,害我很想換主題,不然修CSS好累

好像有個OceanWP的模組可以用用看,希望可以找到合適我的主題RRRR