作者查詢 / springman

總覽項目：發文 | 留言 | 暱稱

作者 springman 在 PTT [ Prob_Solve ] 看板的留言(推文), 共89則

限定看板：Prob_Solve

看板排序：

全部Stock19553Gossiping9970Christianity1835ChangHua1760car1751nCoV20191329Lifeismoney1319HatePolitics1305EZsoft786NBA734MobileComm708Tennis705Browsers586VoIP554LaTeX544Disabled511Office454Google433AfterPhD428biker384IME381Broad_Band350Jeremy_Lin296IA293Windows241JesusLove206Instant_Mess150DYU148C_and_CPP147Free_box146Linux143study133AntiVirus130swim115Federer96Math96Badminton95Android93ONE_PIECE89Prob_Solve89Tech_Job87Teacher71Education61Golf50sky44Nets41PhD40Law-Service39ask-why37Programming37NetRumor32FITNESS31Fix-Network24iOS24MLB20Blog19Brethren19teaching16RegExp14AVEncode13AudioPlayer12Chiayi12Hornets11ask10DV10Kaohsiung10Lakers10BigPeitou9BigShiLin9ChungLi9Gov_owned9Hawks9Hsinchu9Keelung9Web_Design9WomenTalk9WorldCup9Ecophilia8Editor8Ajax7Bunco7Japan_Travel6java6JinYong6StockPicket6DSLR5Football5Knicks5GossipPicket4home-sale4joke4L_TalkandCha4LAW4Miaoli4specialman4Test4TW-F-Tennis4CD-R3Insurance3movie3NSwitch3Option3Rockets3SYSOP3tabletennis3UTAH-JAZZ3Wizards3Baseball2Celtics2ChicagoBulls2Facebook2Finance2MenTalk2NTUT_Talk2PHP2Siam-Star2Storage_Zone2Ang_Lee1Conan1Database1Donate-Blood1FCU_COOP1FCU_Talk1gay1HsinTien1Hualien1hwai1I-Lan1MAC1Mavericks1MdnCNhistory1money1MuscleBeach1Nadal1Nangang1NCU_Talk1PACERS1PingTung1Python1Salary1Tainan1TamShui1TW-history1TW-M-Tennis1WorkinChina1WorldCupGG1YoungArtist1<< 收起看板(147)

首頁

尾頁

Re: [問題] 給定n個排好序的整數陣列找中位數

[ Prob_Solve ]8 留言, 推噓總分: +3

作者: DJWS - 發表於 2014/10/15 07:16(9年前)

7^F推springman: 您們已經想得比我多了 ^_^。10/15 08:17

Re: [問題] 給定n個排好序的整數陣列找中位數

[ Prob_Solve ]23 留言, 推噓總分: +5

作者: DJWS - 發表於 2014/10/14 07:56(9年前)

1^F推springman: 其實就是用 median of median 的演算法，只是找到10/14 09:24

2^F→springman: median of median m 之後，用 binary search 找出10/14 09:25

3^F→springman: 每個排序的陣列中有幾個元素比 m 小，看看要找的10/14 09:25

4^F→springman: median 比 m 大還是比 m 小。10/14 09:26

5^F→springman: 雖然每次可能只能減少 1/4 的元素，不過沒關係。10/14 09:26

6^F→springman: 每次花的時間，理論值是 O(n) 找 median of median10/14 09:27

7^F→springman: O(n log n) 找比 m 小的元素個數。10/14 09:28

8^F→springman: 總共應該只需要花 O(log n) 次10/14 09:28

9^F→springman: 每次都要使用排序好的陣列。10/14 09:29

11^F推springman: 因為 n 個 size 為 n 的數列已經排序好了10/14 13:12

12^F→springman: 要算有幾個元素比 m 小時，並不是拿 n^2 個元素來比較10/14 13:13

13^F→springman: 而是去每個數列做 binary search，所以時間是 O(nlogn)10/14 13:13

15^F推springman: 每一個數列是哪個範圍的元素在候選名單中需要記下來10/14 18:21

16^F→springman: 候選範圍的資料的 median 同樣可以找 median。10/14 18:21

[問題] 給定n個排好序的整數陣列找中位數

[ Prob_Solve ]2 留言, 推噓總分: +1

作者: FRAXIS - 發表於 2014/10/14 06:47(9年前)

1^F推springman: 感覺上有機會比 O(n^2) 小，只是還蠻複雜的。10/14 08:54

2^F→springman: 有空來想想程式要怎麼寫好了。10/14 08:56

[問題] 演算法問題

[ Prob_Solve ]12 留言, 推噓總分: +7

作者: cutekid - 發表於 2014/10/03 08:54(9年前)

5^F推springman: merge sort 可以做到「只能相鄰字母交換」嗎？10/03 20:06

6^F→springman: 感覺上好像 bubble sort 與 inersetion sort 可以。10/03 20:07

7^F→springman: 抱歉，打錯字，insertion sort。10/03 20:08

12^F推springman: 說得也是，只是要計算交換幾次而已，謝謝。10/04 20:10

[問題] 決定性(判定)問題的三種說法

[ Prob_Solve ]1 留言, 推噓總分: +1

作者: dharma - 發表於 2014/07/29 08:33(9年前)

1^F推springman:維基的解釋是正確的，算是它的定義。就是是非題。07/29 09:35

[問題] 驗證某數是否為質數是NP問題

[ Prob_Solve ]2 留言, 推噓總分: +1

作者: dharma - 發表於 2014/06/01 10:54(10年前)

2^F推springman:驗證的時間是 polynomial time 的問題就是 NP 問題。06/01 15:35

Re: [問題] 用induction證明無向圖必有一點為non-cut

[ Prob_Solve ]1 留言, 推噓總分: +1

作者: Leon - 發表於 2013/11/04 11:34(10年前)

1^F推springman:good11/04 16:13

[問題] 用induction證明無向圖必有一點為non-cut

[ Prob_Solve ]8 留言, 推噓總分: +4

作者: jvvbn0601 - 發表於 2013/10/30 21:14(10年前)

4^F推springman:若是沒有 cycle 的話，找一條最長的 path，它的兩個端點11/03 17:01

5^F→springman:都是 non-cut。就算是有 cycle，似乎也是如此。11/03 17:02

6^F推springman:證明應該很簡單，最長的 path 的端與不在 path 上的點11/04 09:27

7^F→springman:一定不相鄰，不然該 path 就不是最長的，所以是 non-cut11/04 09:27

8^F→springman:所謂的最長應該是 maximal length、不是 maximum length11/04 09:33

[問題] Turbo 版老鼠走迷宮..

[ Prob_Solve ]8 留言, 推噓總分: +2

作者: EdisonX - 發表於 2012/11/06 15:42(11年前)

1^F推springman:最短路徑應該是用 BFS、用 queue 不要用 stack。11/06 16:08

[問題] heapsort

[ Prob_Solve ]6 留言, 推噓總分: +1

作者: mqazz1 - 發表於 2012/01/07 21:09(12年前)

1^F推springman:那個答案是對的。只是我總覺得應該建 k+1 個元素的01/08 06:09

2^F→springman:minimum heap 就可以，為什麼需要 2k 個元素呢？01/08 06:09

3^F→springman:將最小的 k+1 個元素建成一個 minimum heap01/08 06:11

4^F→springman:輸出最小值、並再加下一個元素進來01/08 06:11

5^F→springman:重複一直做應該就可從小輸出到大才對01/08 06:12

6^F→springman:從中間做起才需要用到 2k 個元素01/08 06:12

首頁

尾頁