Re: [問題] 排序演算法 可逆式
假設已知序列有N個值 包含n個0跟m個1
那排好的序列會長成 [0..n個..01..m個1..1]
我的想法是
從最初的序列去看 最少要做多少次0&1的swap才會得到排好的序列
Ex1: a[1 0 0 1 0] => 一次 swap(a[0],a[4]) 就好了
Ex2: a[1 0 1 0 0] => 兩次 swap(a[0],a[4]), swap(a[2],a[3])
每一個swap 就用兩個數字去存 ex: (0,4) (2,3)
這樣記錄所需要的記憶體 = min(n, m)*2
大部分的情況都會 < N
只有最壞的情況 就是0跟1的數量相同 然後排列完全相反 (ex: 111000)
所需要的空間剛好等於 (N/2) * 2 = N
解決這個問題方法很多 你可以拿一個特殊的值去記錄這種情況=.=
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.166.83.80
※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1413907898.A.DAC.html
※ 編輯: hardyyeh (218.166.83.80), 10/22/2014 00:13:27
推
10/22 00:16, , 1F
10/22 00:16, 1F
→
10/22 00:16, , 2F
10/22 00:16, 2F
→
10/22 00:20, , 3F
10/22 00:20, 3F
→
10/22 00:21, , 4F
10/22 00:21, 4F
→
10/22 00:21, , 5F
10/22 00:21, 5F
→
10/22 00:23, , 6F
10/22 00:23, 6F
→
10/22 00:25, , 7F
10/22 00:25, 7F
推
10/22 00:28, , 8F
10/22 00:28, 8F
→
10/22 01:05, , 9F
10/22 01:05, 9F
→
10/22 01:07, , 10F
10/22 01:07, 10F
推
10/22 01:22, , 11F
10/22 01:22, 11F
→
10/22 01:22, , 12F
10/22 01:22, 12F
討論串 (同標題文章)