反interleave该怎么做？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

反interleave该怎么做？

反interleave该怎么做？# JobHunting - 待字闺中

c*t2011-11-19 08:11

1 楼

过去这个班上讨论了interleave数组的问题，
给定数组： A B C D E 1 2 3 4 5
输出: A 1 B 2 C 3 D 4 E 5
可是这个问题的对偶题，就是说
给定数组：A 1 B 2 C 3 D 4 E 5
如何in-place把数组变成 A B C D E 1 2 3 4 5
?
谢谢了！

b*g2011-11-19 08:11

2 楼

我觉得就是把ABCD变成数字，然后排序。
1. scan array once to find minimum number, min
2. for each character c1, c1 -'A' - min
3. quick sort
O(nlogn)

n*w2011-11-19 08:11

3 楼

有O（n）解，站内搜索。

【在 b******g 的大作中提到】

: 我觉得就是把ABCD变成数字，然后排序。
: 1. scan array once to find minimum number, min
: 2. for each character c1, c1 -'A' - min
: 3. quick sort
: O(nlogn)

d*d2011-11-19 08:11

4 楼

have fun
void swap_cs(char *a, int i, int j, int n){
for(int k = 0; kchar temp = a[i+k];
a[i+k]=a[j+k];
a[j+k] = temp;
}
return;
}
void switch_string_back(char *a, int i, int j){
if( j-i <=1)
return;
int mid = (i+j)/2;
switch_string_back(a, i, mid);
switch_string_back(a, mid+1, j);
int first_half_mid = (i+mid)/2;
int first_half_n = mid-i+1;
if( first_half_n & 1){
swap_cs(a, first_half_mid+1, j- first_half_n/2 + 1, first_half_n/2);
}else{
swap_cs(a, first_half_mid+1, mid+1, first_half_n/2);
}
return;
}

b*g2011-11-19 08:11

5 楼

我没搜索，不过我想到了冒泡算法。
因为是interleaving而且字符和数字已经排好序了, 所以就是简单的扫一遍，过程中数
字和后面的字符交换。
准确讲是O(n/2)=>O(n).

【在 n*******w 的大作中提到】

: 有O（n）解，站内搜索。

r*g2011-11-19 08:11

6 楼

难道不是一样采用分枝法？
原题的解答是
A B C D E 1 2 3 4 5 => A B C 1 2 3 D E 4 5 => ....
就是说先交换在分治
你现在这个题的解答是
A 1 B 2 C 3 D 4 E 5 => A B C 1 2 3 D E 4 5 => 。。。。
先分治再交换。
O(n)的算法就算了，nlogn挺好的了。

【在 c*********t 的大作中提到】

: 过去这个班上讨论了interleave数组的问题，
: 给定数组： A B C D E 1 2 3 4 5
: 输出: A 1 B 2 C 3 D 4 E 5
: 可是这个问题的对偶题，就是说
: 给定数组：A 1 B 2 C 3 D 4 E 5
: 如何in-place把数组变成 A B C D E 1 2 3 4 5
: ?
: 谢谢了！

f*t2011-11-19 08:11

7 楼

“过程中数字和后面的字符交换”不是O(n)吧

【在 b******g 的大作中提到】

: 我没搜索，不过我想到了冒泡算法。
: 因为是interleaving而且字符和数字已经排好序了, 所以就是简单的扫一遍，过程中数
: 字和后面的字符交换。
: 准确讲是O(n/2)=>O(n).

b*g2011-11-19 08:11

8 楼

提醒的对，我想简单了。那怎么才能O（n）？有没有个大概的思路？我找不到版上的答
案。

【在 f*******t 的大作中提到】

: “过程中数字和后面的字符交换”不是O(n)吧

r*g2011-11-19 08:11

9 楼

我觉得O(nlogn)已经够好了，对于原题，这个版讨论了很多，一个叫shyx(可能记错了)
的id给了个链接上面有O(n)的解答，还用到了素数的东西。
但是这个版面很多人给的O(n)的解答其实不是O(n)，我当时还专门比较过，结果发现基
于分治法的O(nlogn)实际运行起来更快，原因是他们把查找链的过程不算做开销，实际
上这个开销对大的输入是很大的。这个链就是需要交换的位置，一个链的意思就是说上
面的元素依次交换。O(n)的办法无非就是找到这样的多个链。

【在 b******g 的大作中提到】

: 提醒的对，我想简单了。那怎么才能O（n）？有没有个大概的思路？我找不到版上的答
: 案。

b*g2011-11-19 08:11

10 楼

学习了。如果还有素数啥的，那我就放弃了。

了)

【在 r*******g 的大作中提到】

: 我觉得O(nlogn)已经够好了，对于原题，这个版讨论了很多，一个叫shyx(可能记错了)
: 的id给了个链接上面有O(n)的解答，还用到了素数的东西。
: 但是这个版面很多人给的O(n)的解答其实不是O(n)，我当时还专门比较过，结果发现基
: 于分治法的O(nlogn)实际运行起来更快，原因是他们把查找链的过程不算做开销，实际
: 上这个开销对大的输入是很大的。这个链就是需要交换的位置，一个链的意思就是说上
: 面的元素依次交换。O(n)的办法无非就是找到这样的多个链。

d*n2011-11-19 08:11

11 楼

here is a O(nlogn) solution, Rotate can be further optimized.
public class InterleaveShuffle {
public static void main(String argv[]) {
int [] arr = {1,2,3,4,5,100,200,300,400,500};
InplaceInterleave(arr, 0, arr.length - 1);
InplaceRestore(arr, 0, arr.length - 1);
}

static void Reverse(int A[], int left, int right)
{
while (left < right) {
int tmp = A[left];
A[left++] = A[right];
A[right--] = tmp;
}
}
static void Rotate(int A[], int left, int right, int piv) {
if(piv != left){
Reverse(A, left, piv - 1);
Reverse(A, piv, right);
}

Reverse(A, left, right);
}

static void InplaceInterleave(int A[], int left, int right) {
if ((right - left) <= 1) return;

int mid = left + (right - left) / 2;
int halfSize = (right - left + 1) / 2;

int leftMid = left + (mid - left) / 2;
int rightMid = (right + mid + 1) / 2;

Rotate(A, leftMid + 1, rightMid, mid + 1);

InplaceInterleave(A, left, mid + halfSize % 2);
InplaceInterleave(A, mid + 1 + halfSize % 2, right);
}

static void InplaceRestore(int A[], int left, int right) {
if ((right - left) <= 1) return;

int mid = left + (right - left) / 2;
int halfSize = (right - left + 1) / 2;

int leftMid = left + (mid - left) / 2;
int rightMid = (right + mid + 1) / 2;

InplaceRestore(A, left, mid + halfSize % 2);
InplaceRestore(A, mid + halfSize % 2 + 1, right);
Rotate(A, leftMid + 1, rightMid, mid + halfSize % 2 +1);
}
}