Re: [问题] 算法问题

楼主: DJWS (...)   2014-10-04 14:40:47
※ 引述《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)
作者: cutekid (可爱小孩子)   2014-10-06 08:18:00
推(Y)
作者: saladim (杀拉顶)   2014-10-13 09:00:00
已晕 推一下 慢慢看 @_@
作者: jainnkae (真是令人期待)   2014-10-17 16:08:00

Links booklink

Contact Us: admin [ a t ] ucptt.com