Re: [问题] 排序算法可逆式 hardyyeh PTT批踢踢实业坊

Re: [问题] 排序算法可逆式

楼主: hardyyeh (阿叶) 2014-10-22 00:11:35

假设已知序列有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
解决这个问题方法很多你可以拿一个特殊的值去记录这种情况=.=

作者: flydragon198 (Richard) 2014-10-22 00:16:00

假设a[]阵列内每个元素(0,1)占1bit，用来记录的swap每个元素无法用1bit储存，所以需要空间是大于N的，

作者: bibo9901 (function(){})() 2014-10-22 00:20:00

只记录 n,m 两个数字就能得到排序后的序列啊

楼主: hardyyeh (阿叶) 2014-10-22 00:21:00

回楼上我是假设他本来用不是用存啦(虽然只有0,1很浪费)如果是要押在 N bit内那我目前还想不到方法To bibo大: 没错但原PO的要求是还原回去本来的序列现在发现这个方法没有省到内存等等自删

作者: flydragon198 (Richard) 2014-10-22 00:28:00

XD C++版没办法删文章喔

作者: Feis (永远睡不着 @@) 2014-10-22 01:05:00

(N - 1) ~ (N - logN/log2) 都还有可能. 可以到 logN 以下?可以的话, 应该蛮酷的~

作者: EdisonX (卡卡兽) 2014-10-22 01:22:00

我想到件事... a --> (排序得) --> b , 可用 xor 去做？这样从 2 个数字降到 1 个数字 ?

继续阅读

[问题] 新手发问--关于C语言如何解读字串?wandering25 [问题] scanf overflow/空值lionheart60 [问题] 排序算法可逆式angelina877 [问题] opencv如何利用循环一次加载多张图raily1151521 [问题] 阵列这个变量的位置musicJD [问题] 字串赋值问题kdok123 Re: [问题] CUDA 多个GPU(Multi GPU) 资料传递问题iHakka [问题] 一个专案里面只执行一个.cpp档unixxxx [问题] 视窗程式ID1234567 Re: [问题] 关于光流法的使用dragon229

Re: [问题] 排序算法 可逆式

Re: [问题] 排序算法可逆式