[问题] 算法问题 cutekid PTT批踢踢实业坊

[问题] 算法问题

楼主: cutekid (可爱小孩子) 2014-10-03 08:54:24

给一字串全由字母 A-Z 组成
将其依字母顺序由小到大排序
限定只能相邻字母两两交换
问至少要交换几次
能排序完成
Ex.
Input : DCBA
Output: 6
请问这有好的算法吗
谢谢 :)

作者: ckc1ark (伪物) 2014-10-03 09:06:00

从merge sort下手

作者: LPH66 (-6.2598534e+18f) 2014-10-03 09:19:00

所求为逆序对的数目, 不过基本上就是 merge sort...

楼主: cutekid (可爱小孩子) 2014-10-03 09:36:00

谢谢 c 大和 L 大L 大好厉害，可以想到是求“逆序对”数目，赞叹！

作者: springman (司布林) 2014-10-03 20:06:00

merge sort 可以做到“只能相邻字母交换”吗？感觉上好像 bubble sort 与 inersetion sort 可以。抱歉，打错字，insertion sort。

作者: johnathan717 (柏良) 2014-10-04 01:31:00

用什么sort都可以,只是merge sort能O(nlgn)算逆序数

作者: DJWS (...) 2014-10-04 14:07:00

那为什么不用counting sort? 听起来更快springman: merge sort不能做到相邻字母交换但是改一改之后可以用来数逆序对

作者: springman (司布林) 2014-10-04 20:10:00

说得也是，只是要计算交换几次而已，谢谢。

继续阅读

Re: [问题] three-cornered dualpika0923 [问题] three-cornered dualcckk3333 [问题]线代算法应用pauliaia Re: [问题] ACM 4846 (Strongly connected component?)bleed1979 [问题] 请问有稳定的RNG吗?preed Re: [问题] ACM 4846 (Strongly connected component?)DJWS Re: [问题] ACM 4846 (Strongly connected component?)scwg [问题] ACM 4846 (Strongly connected component?)iamnotgm [问题] 电脑只有记忆排序搜寻三功能作复杂组合dharma [问题] 复杂度searchtree

Contact Us: admin [ a t ] ucptt.com