假設已知序列有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
解決這個問題方法很多 你可以拿一個特殊的值去記錄這種情況=.=