作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 演算法问题
时间Sat Oct 4 14:40:47 2014
※ 引述《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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1412404852.A.586.html
※ 编辑: DJWS (111.250.88.236), 10/04/2014 14:47:36
1F：推 cutekid: 推(Y) 10/06 08:18
2F：推 saladim: 已晕 推一下 慢慢看 @_@ 10/13 09:00
3F：推 jainnkae: 推 10/17 16:08