PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 陣列中的比自己小的數字

看板Prob_Solve (計算數學 Problem Solving)作者jason21716 (阿鴻)時間8年前 (2016/10/31 14:00)推噓8(8推 0噓 13→)

留言21則, 9人參與討論串1/1

各位好，小弟有一個演算法的問題想請教各位大大有一個陣列，內有若N個不相同且隨機排列的數字如：2 8 6 1 9 10 13 0 我需要依照陣列順序把排在自己之後而且比自己小的數字印出來像這樣： 2 1 2 0 8 6 8 1 8 0 6 1 6 0 9 0 10 0 13 0 我知道如果用迴圈一個一個檢查總是有結果的但是演算法效率是O(n^2) 想請問各位有沒有比O(n^2)更快的做法?? 我想了很久，但都沒有比較好的解法... 不好意思麻煩各位了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.113.124.157 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1477893613.A.FC7.html

推

ddavid

10/31 14:35, , 1^F

10/31 14:35, 1^F

→

ddavid

10/31 14:36, , 2^F

10/31 14:36, 2^F

是呀...這一點讓人很頭疼... 那如果說今天在不要求順序的狀況下，有可能提升速度嗎...

推

ddavid

10/31 14:50, , 3^F

10/31 14:50, 3^F

→

ddavid

10/31 14:52, , 4^F

10/31 14:52, 4^F

推

CaptainH

10/31 15:01, , 5^F

10/31 15:01, 5^F

mergeSort嗎... 可是mergeSort在merge時一次都只看左右兩邊各一個數字如果今天左邊的陣列數字全都比右邊的大，那就會出問題了... 但這似乎也是個好主意...透過merge時將左右兩邊排好我讓左邊的最大值開始掃描右邊的最小值，左>右就輸出值對，左<右就換左遍次大的重來一遍左邊全部掃完之後就把兩邊merge起來可是演算法效率... mergeSort本身效率是O(nlogn)，但因為要掃描左右兩邊的大小勢必得再加上這個步驟的成本... 剛剛拿大師定理算了一下，最糟糕的狀況(已經由大排到小)是O(n^2) 最好的狀況(由小到大)是O(nlogn)，平均狀況的話我在算算看不過似乎是可行的做法.... .... 不行，平均狀況的結果算來算去應該也會是O(n^2) 還需要更快的方法才行

→

pttworld

10/31 16:29, , 6^F

10/31 16:29, 6^F

是像這樣嗎? 原陣列 2 8 6 1 9 10 13 0 索引 0 1 2 3 4 5 6 7 排序後 value 0 1 2 6 8 9 10 13 index 7 3 0 2 1 4 5 6 然後從13開始，往前找index比它還大的數字嗎? 可是這樣子的效率還是O(n^2).... 或許是我誤解大大的意思了?? ※ 編輯: jason21716 (120.113.124.157), 10/31/2016 17:40:14

推

s89162504

10/31 19:52, , 7^F

10/31 19:52, 7^F

→

pttworld

10/31 20:05, , 8^F

10/31 20:05, 8^F

推

c225

11/01 00:20, , 9^F

11/01 00:20, 9^F