1
clww 2013-03-29 11:45:38 +08:00
结果应该不确定吧
一个简单的方案:从左到右读,A[i]!=B[i], A[i]==B[j], [A[i],A[j]]换 |
2
AustinLee OP @clww 想想 在数学上确实 是不确定的
但是应该有个 最简的 就是交换次数最少的 算法 这样 我把题目换一下 数组 A[1,2,3,4] 交换为 B[2,3,1,4] 最少要交换 几次 分别要交换哪几个index |
3
lookhi 2013-03-29 13:33:11 +08:00
自觉上要剪枝? 实际应该就直接交换就好了吧。
交换是独立的,对其他位置不定的没影响,也没啥好处吧 |
4
sohoer 2013-03-29 13:53:08 +08:00
Compute Levenshtein distance
跟这个算法有点关系 |
5
AustinLee OP |
6
AustinLee OP @sohoer 这个 直接把我玩傻了 汗http://en.wikipedia.org/wiki/Levenshtein_distance
|
8
wog 2013-03-30 17:26:04 +08:00
其实,碰见这种问题,如果我实在做不出来都是用随机算法来做的
我试了下用随机算法来做,用c++写了个小程序,(没看明白你那个题目是不是只能交换相邻的两个数字,不过我写程序是按照只能交换相邻位置的两个元素来写的) 在数组长度小于6的时候都非常稳定, A[1,2,3,4] B[2,3,1,4] 2 real 0m0.291s user 0m0.008s sys 0m0.284s ==================== A = {1, 2, 3, 4,5}; B = {2, 3, 5, 1, 4}; 4 real 0m0.295s user 0m0.008s sys 0m0.284s ======================== A = {1, 2, 3, 4, 5, 6}; B = {6, 2, 3, 5, 1, 4}; 11 real 0m0.338s user 0m0.064s sys 0m0.272s 在这之前,我程序的尝试次数定在1024,结果几乎没有什么浮动 ====================== A = {1, 2, 3, 4, 5, 6, 7}; B = {6, 2, 7, 3, 5, 1, 4}; 17 real 0m21.271s user 0m3.632s sys 0m17.616s 在这里如果尝试次数还是1024的话,得到的结果浮动很大,所以直接改成65535了 ============================================== A = {1, 2, 3, 4, 5, 6,7,8}; B = {6, 2, 7, 3, 5, 8,1,4,}; 19 real 0m19.241s user 0m1.596s sys 0m17.624s 还是尝试65535次 不过话说回来,这个问题用贪心算法和我用的这个方法,只能得到近似最优解,要真正准确的算出来最有解,还是得用动态规划,不过这个动态规划是需要完全遍历所有情况的,我觉得要实现的话不太现实 |
9
wog 2013-03-30 17:31:16 +08:00
上面那个数字是需要交换的次数,为了节省空间,就没贴具体的交换方式
|
10
wy315700 2013-03-30 21:22:02 +08:00
|
12
wodesuck 2013-04-01 11:57:01 +08:00 via Android
这是逆序对问题吧,用归并排序或者线段树都能在O(nlogn)解决
|
13
AustinLee OP @wodesuck http://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作 查了下 不对啦 |
14
wy315700 2013-04-01 15:18:39 +08:00
|