s******0
发帖数: 19 | 1 一个数组a1,a2,a3...an,b1,b2,b3...bn, 怎么in place地转化成
a1,b1,a2,b2,a3,b3...an,bn
除了O(n2)的brute force觉得想不出其他解法:(
谢谢！ | B*******1
发帖数: 2454 | 2 直接跪了。
★ 发自iPhone App: ChineseWeb 7.3
【在 s******0 的大作中提到】
: 一个数组a1,a2,a3...an,b1,b2,b3...bn, 怎么in place地转化成
: a1,b1,a2,b2,a3,b3...an,bn
: 除了O(n2)的brute force觉得想不出其他解法:(
: 谢谢！
| s******0
发帖数: 19 | 3 什么意思？ 太简单了？
【在 B*******1 的大作中提到】
: 直接跪了。
:
: ★ 发自iPhone App: ChineseWeb 7.3
| r*****e
发帖数: 792 | 4 前一段讨论过啊，nlogn的算法不算太难，不用考虑奇偶。
【在 s******0 的大作中提到】
: 一个数组a1,a2,a3...an,b1,b2,b3...bn, 怎么in place地转化成
: a1,b1,a2,b2,a3,b3...an,bn
: 除了O(n2)的brute force觉得想不出其他解法:(
: 谢谢！
| s******0
发帖数: 19 | 5 请教怎么做？
【在 r*****e 的大作中提到】
: 前一段讨论过啊，nlogn的算法不算太难，不用考虑奇偶。
| r*****e
发帖数: 792 | 6 void arrayShuffle(vector &v, int first, int last) {
int mid, halfLen=(last-first)/2;
if (last-first<=2)//already in place
return;
if (last-first==4) {//swap middle two
swap(v[first+1], v[first+2]);
return;
}
/* regular cases */
mid = halfLen/2+first;
vector::iterator it = v.begin();
reverse(it+mid, it+mid+halfLen);//reverse entire mid section first
reverse(it+mid, it+mid+(mid-first));
reverse(it+mid+(mid-first), it+mid+halfLen);
arrayShuffle(v, first, first+2*(mid-first));
arrayShuffle(v, first+2*(mid-first), last);
}
【在 s******0 的大作中提到】
: 请教怎么做？
| s******0
发帖数: 19 | 7 你好厉害！谢谢阿～
【在 r*****e 的大作中提到】
: void arrayShuffle(vector &v, int first, int last) {
: int mid, halfLen=(last-first)/2;
: if (last-first<=2)//already in place
: return;
: if (last-first==4) {//swap middle two
: swap(v[first+1], v[first+2]);
: return;
: }
: /* regular cases */
: mid = halfLen/2+first;
| r*****e
发帖数: 792 | 8 显然不是现写的啊，呵呵。
不过明白思想后再写就快多了。
【在 s******0 的大作中提到】
: 你好厉害！谢谢阿～
| j*****n
发帖数: 1545 | 9 可以这样， 先把中间的1对, 然后swap的2对，然后3对..
a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 -- swap (a5,b1)
a1 a2 a3 a4 b1 a5 b2 b3 b4 b5 -- swap (a4,b1) (a5,b2)
a1 a2 a3 b1 a4 b2 a5 b3 b4 b5 -- swap (a3,b1) (a4,b2) (a5,b3)
a1 a2 b1 a3 b2 a4 b3 a5 b4 b5 -- swap (a2,b1) (a3,b2) (a4,b3) (a5,b4)
a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 -- done
【在 s******0 的大作中提到】
: 一个数组a1,a2,a3...an,b1,b2,b3...bn, 怎么in place地转化成
: a1,b1,a2,b2,a3,b3...an,bn
: 除了O(n2)的brute force觉得想不出其他解法:(
: 谢谢！
| s*******d
发帖数: 34 | 10 没看明白。能解释一下吗？
【在 r*****e 的大作中提到】
: void arrayShuffle(vector &v, int first, int last) {
: int mid, halfLen=(last-first)/2;
: if (last-first<=2)//already in place
: return;
: if (last-first==4) {//swap middle two
: swap(v[first+1], v[first+2]);
: return;
: }
: /* regular cases */
: mid = halfLen/2+first;
| b******v
发帖数: 1493 | 11 这是mxn矩阵 in-place 转置问题。你给的例子是2xn矩阵。
关于这个问题的解法，可以看下面这篇paper
http://www.springerlink.com/content/9755264224612x75/
【在 s******0 的大作中提到】
: 一个数组a1,a2,a3...an,b1,b2,b3...bn, 怎么in place地转化成
: a1,b1,a2,b2,a3,b3...an,bn
: 除了O(n2)的brute force觉得想不出其他解法:(
: 谢谢！
| r*****e
发帖数: 792 | |
|
