Re: [問題] 演算法問題
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間10年前 (2014/10/04 14:40)推噓3(3推 0噓 0→)留言3則, 3人參與討論串6/8 (看更多)
※ 引述《cutekid (可愛小孩子)》之銘言：
: 給一字串全由字母 A-Z 組成
: 將其依字母順序由小到大排序
: 限定只能相鄰字母兩兩交換
: 問至少要交換幾次
: 能排序完成
: Ex.
: Input : DCBA
: Output: 6
: 請問這有好的算法嗎
: 謝謝 :)
相鄰交換 -> 逆序數 -> 修改merge sort來計算逆序數
-> 基於兩兩比較的排序法都可以算逆序數
這套流程，推文已經講得很清楚了
這裡講另外一個基於 counting sort 與 prefix sum 的方法
int n = 4;
char str[] = "DCBA";
int count[26] = {};
int ans = 0;
for (int i = 0; i < n; ++i)
{
int index = str[i] - 'A';
count[ index ] ++;
// ans += sum( count[index + 1] ... count[26 - 1] );
for (int j = index + 1 ; j < 26; ++j)
ans += count[j];
}
print ans;
時間複雜度 O(n * 26) = O(n)
或者也可以用 binary indexed tree，時間複雜度 O(n * lg(26)) = O(n)
或者也可以用其他的 prefix sum 演算法
由於輸入是有界整數，我猜應該可以做到 O(n * lglg(26))，不過還是 O(n)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.88.236
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1412404852.A.586.html
※ 編輯: DJWS (111.250.88.236), 10/04/2014 14:47:36
推
10/06 08:18, , 1F
10/06 08:18, 1F
推
10/13 09:00, , 2F
10/13 09:00, 2F
推
10/17 16:08, , 3F
10/17 16:08, 3F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
