关于&给定的一个1,2,3组成的数字序列，排成升序所需的最少交换次数&这个算法有两个很巧妙的解答:例如：序列： 2 2 1 3 3 3 2 3 1
要变成序列： 1 1 2 2 2 3 3 3 3最少需要的交换次数为4。
解法一：设 cAB 为在A位置上的B的数目，则***为：c21 + c31 + (c21 & c12 ? c23 + c21 - c12 : c32 + c12 - c21)按照这一方法，再看上面那个例子：c21 + c31 + (c21 & c12 ? c23 + c21 - c12 : c32 + c12 - c21)=1
1 )=4根据这个公式算得的***为4，其他的例子我也测试过，确实是正确的。
解法二：统计在应该是1的位置出现2的个数为a1;统计在应该是2的位置出现1的个数为a2；统计应该是1、2的位置出现3的个数为a3；那么最少交换次数为：a3 + (a1 & a2 ? a1: a2)果然根据这个公式算得的***为4，其他的例子我也测试过，确实是正确的。
请问这两个方法中的公式是什么道理，为什么这样列？求详细解释！关于这个算法题如果有更好的解答方法的话也欢迎回答！谢谢
该问题被发起重新开启投票
投票剩余时间：
之前被关闭原因：
该问题被发起删除投票
投票剩余时间：
距离悬赏到期还有：
参与关闭投票者：
关闭原因：
该问题已经被锁定
锁定原因：（）
保护原因：避免来自新用户不合宜或无意义的致谢、跟帖***。
该问题已成功删除，仅对您可见，其他人不能够查看。
将数字（或者别的什么东西）以任意方式重新排列的过程称为置换，置换总是可以唯一地写成若干个轮换的组合，所谓轮换是指a-&b-&c-&d-&a这样的a,b,c,d四个数循环着交换位置的过程，比如说
a b c d e f gc e f a g b d
就可以写成(acfbegd)
而a b c d e f ga e b c d g f可以写成(a)(bedc)(fg)
而通过交换来完成某个置换的最小次数就等于通过交换完成这些轮换的次数，轮换长度为N的需要N-1次，因此总的次数就等于元素个数 - 轮换个数
回到原问题，显然就是找出一个置换，使得能将数列调整成目标状态，而且轮换个数最多。显然优先使用一轮换（不变），其次二轮换，最后是三轮换。也就是：1-1、2-2、3-3的不交换（一轮换），1-2和2-1，1-3和3-1,2-3和3-2配对成二轮换，剩下的形成1-2-3或1-3-2的三轮换。最后的交换次数是二轮换的数量加上三轮换的数量乘以二。用公式表示的话就是：min(c12,c21) + min(c13,c31) + min(c23,c32) + |c12 - c21| * 2（因为剩余的不能匹配的1-2或者2-1每个都会对应一个三轮换）
注意到min(c12,c21) + |c12 - c21| = max(c12,c21)而min(c12,c21) + max(c12,c21) = c12 + c21因此min(c12,c21) + max(c12,c21) = min(c12,c21) + min(c12,c21) + |c12 - c21|= 2 * min(c12,c21) + |c12 - c21| = c12 + c21同理2 * min(c13,c31) + |c13 - c31| = c13 + c312 * min(c23,c32) + |c23 - c32| = c23 + c32
而|c12 - c21| = |c13 - c31| = |c23 - c32|（都是三轮换个数）把前面三个等式左右两边分别相加得到：2 * min(c12,c21) + 2 * min(c13,c31) + 2 * min(c23,c32) + 3 * |c12 - c21| = c12 + c21 + c13 + c31+ c23 + c32
因此min(c12,c21) + min(c13,c31) + min(c23,c32) + |c12 - c21| * 2= 0.5 * (c12 + c21 + c13 + c31+ c23 + c32 + |c23 - c32|)
然后：注意到c11 + c12 + c13 = 1的个数 = c11 + c21 + c31因此c12 + c13 = c21 + c31因此0.5 * (c12 + c21 + c13 + c31+ c23 + c32 + |c23 - c32|)= c12 + c13 + 0.5 * (c23 + c32 + |c23 - c32|)而由之前的结论：c23 + c32 + |c23 - c32| = 2 * max(c23,c32)因此原式 = c12 + c13 + max(c23,c32)和解法二等效（只不过1,2,3的顺序有差异）
而解法一：c21 + c31 + (c21 & c12 ? c23 + c21 - c12 : c32 + c12 - c21)由于c23 + c21 = c32 + c12，因此原式 = c21 + c31 + c32 + c12 - min(c21,c12)= c31 + c32 + (c21 + c12 - min(c21,c12))= c31 + c32 + max(c21,c12)可见也是等效的
不是您所需，查看更多相关问题与***
德问是一个专业的编程问答社区，请
后再提交***
没有相关问题
关注该问题的人
共被浏览 (4442) 次| 521: Web server is down
Los Angeles
Cloudflare
What happened?
The web server is not returning a connection. As a result, the web page is not displaying.
What can I do?
If you are a visitor of this website:
Please try again in a few minutes.
If you are the owner of this website:
Contact your hosting provider letting them know your web server is not responding. .