Google经典题目一问 - 未名空间MITBBS历史存档

Z*Z2010-04-22 07:04

1 楼

Given a Data Structure having first n integers and next n chars. A = i1 i2 i
3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elemen
ts of the array ass A = i1 c1 i2 c2 ... in cn
O（nlgn)的算法我知道。有没有O（n)的算法？

m*g2010-04-22 07:04

2 楼

理论上似乎完全可行
比如
1. int temp
move c2 to i2, i2 to temp
move temp (i2) to i3, i3 to temp
move temp (i3) to i5, i5 to temp
.....
难点就是如何把代码写出来而且写的整洁

x*r2010-04-22 07:04

3 楼

请问一下nlgn怎么做呢？

i2 i
elemen

【在 Z*****Z 的大作中提到】

: Given a Data Structure having first n integers and next n chars. A = i1 i2 i
: 3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elemen
: ts of the array ass A = i1 c1 i2 c2 ... in cn
: O（nlgn)的算法我知道。有没有O（n)的算法？

j*l2010-04-22 07:04

4 楼

题目描述搞那么复杂，还不如用0,1或者a,b描述的习惯

y*c2010-04-22 07:04

5 楼

O(n) algorithm exists.
The problem with mustang's comment is one cycle will not cover all the
elements but it's the way to go.

x*32010-04-22 07:04

6 楼

能具体说说吗，我nlgn和O(n)的一个都不知道, 3q

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

: O(n) algorithm exists.
: The problem with mustang's comment is one cycle will not cover all the
: elements but it's the way to go.

y*c2010-04-22 07:04

7 楼

1. O(nlogn)
divide and conquer
abcd1234 -> ab12cd34 -> a1b2c3d4
T(n) = O(n) + 2T(n/2) -> O(nlgn)
2 O(n)
This is just like matrix transposition using O(1) space.
If we use row major, the absolute position for a[i][j] is i*n + j. After
transposing, it goes to j* m + i = i'*n + j', which in turn will go to j'* m
+ i' and so on. There is a paper on the proof.

x*32010-04-22 07:04

8 楼

赞，多谢了

j'* m

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

: 1. O(nlogn)
: divide and conquer
: abcd1234 -> ab12cd34 -> a1b2c3d4
: T(n) = O(n) + 2T(n/2) -> O(nlgn)
: 2 O(n)
: This is just like matrix transposition using O(1) space.
: If we use row major, the absolute position for a[i][j] is i*n + j. After
: transposing, it goes to j* m + i = i'*n + j', which in turn will go to j'* m
: + i' and so on. There is a paper on the proof.

Z*Z2010-04-22 07:04

9 楼

没看太懂。我原来一直把矩阵转置当成一个没解决的问题。不知道你的解释是一个矩阵
转置的一般性解法，还是利用了这个矩阵只有2行的性质呢？

m

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

: 1. O(nlogn)
: divide and conquer
: abcd1234 -> ab12cd34 -> a1b2c3d4
: T(n) = O(n) + 2T(n/2) -> O(nlgn)
: 2 O(n)
: This is just like matrix transposition using O(1) space.
: If we use row major, the absolute position for a[i][j] is i*n + j. After
: transposing, it goes to j* m + i = i'*n + j', which in turn will go to j'* m
: + i' and so on. There is a paper on the proof.

y*c2010-04-22 07:04

10 楼

What I described is a general case, which works for any matrix, including
your 2 rows problem. If you want O(n) algorithm, I think that's the way to
go.
This is the paper.
Transposing a Matrix without Incurring Additional Storage

Z*Z2010-04-22 07:04

11 楼

十分感谢

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

: What I described is a general case, which works for any matrix, including
: your 2 rows problem. If you want O(n) algorithm, I think that's the way to
: go.
: This is the paper.
: Transposing a Matrix without Incurring Additional Storage

K*g2010-04-22 07:04

12 楼

能不能说清楚点呢？你那个O（n）怎么用到这个题目上来?矩阵转置可以这么做是因为任何一个元素与另外一个交换就可以做到，但是这个题目好像不可以。不知道为什么“This is just like matrix transposition using O(1) space”

m

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

: 1. O(nlogn)
: divide and conquer
: abcd1234 -> ab12cd34 -> a1b2c3d4
: T(n) = O(n) + 2T(n/2) -> O(nlgn)
: 2 O(n)
: This is just like matrix transposition using O(1) space.
: If we use row major, the absolute position for a[i][j] is i*n + j. After
: transposing, it goes to j* m + i = i'*n + j', which in turn will go to j'* m
: + i' and so on. There is a paper on the proof.

h*62010-04-22 07:04

13 楼

我想了一种办法，不过只适用于二行的情况。
假设数组a长度为2n，下标为[0, 2n)
显然a[0]不需要交换，我们可以依次寻找[1, 2n)的数需要和哪个数交换即可。
循环i于[1, 2n), 假设a[i]与a[k]交换，则一定有k>i
当i位于前一半，即[1, n)，定义一个队列，初始为空
若i为奇数，k = (i-1)/2+n
若i为偶数，k = 队列第一个数并弹出
两种情况都需要把k放入队列尾
若i位于后一半，即[n, 2n)，销毁队列
若i为奇数，k = (i-1)/2+n
若i为偶数，不需要交换

Z*Z2010-04-22 07:04

14 楼

有一点不明白，假设n为奇数，当循环走到i = n-1的时候，也就是i指向前半部分的最后
一个元素（想象一下，这个元素应该是最终输出的倒数第二个元素）。根据算法，这个
元素入队。之后，走到了后半部分，这个队列就被销毁了。所以那个元素就lost了？

【在 h**6 的大作中提到】

: 我想了一种办法，不过只适用于二行的情况。
: 假设数组a长度为2n，下标为[0, 2n)
: 显然a[0]不需要交换，我们可以依次寻找[1, 2n)的数需要和哪个数交换即可。
: 循环i于[1, 2n), 假设a[i]与a[k]交换，则一定有k>i
: 当i位于前一半，即[1, n)，定义一个队列，初始为空
: 若i为奇数，k = (i-1)/2+n
: 若i为偶数，k = 队列第一个数并弹出
: 两种情况都需要把k放入队列尾
: 若i位于后一半，即[n, 2n)，销毁队列
: 若i为奇数，k = (i-1)/2+n

h*62010-04-22 07:04

15 楼

嘴上不太好说，给你举个实例吧，n无论奇偶这个算法都有效的。
queue = empty
0 1 2 3 4 5 6 7 8 9
k[1] = 5
queue = 5
0 5 2 3 4 1 6 7 8 9
k[2] = 5
queue = 5
0 5 1 3 4 2 6 7 8 9
k[3] = 6
queue = 56
0 5 1 6 4 2 3 7 8 9
k[4] = 5
queue = 65
0 5 1 6 2 4 3 7 8 9
k[5] = 7
0 5 1 6 2 7 3 4 8 9
k[6] continue
0 5 1 6 2 7 3 4 8 9
k[7] = 8
0 5 1 6 2 7 3 8 4 9
k[8] continue
0 5 1 6 2 7 3 8 4 9

Z*Z2010-04-22 07:04

16 楼

明白了，队列里装的是k，不是元素。
强！

【在 h**6 的大作中提到】

: 嘴上不太好说，给你举个实例吧，n无论奇偶这个算法都有效的。
: queue = empty
: 0 1 2 3 4 5 6 7 8 9
: k[1] = 5
: queue = 5
: 0 5 2 3 4 1 6 7 8 9
: k[2] = 5
: queue = 5
: 0 5 1 3 4 2 6 7 8 9
: k[3] = 6

K*g2010-04-22 07:04

17 楼

基本上是对的，但是有一点要做修改：
不需要区分i是在前一半还是后一半，每次都要把k放入队列，也不要把队列销毁。当i
是偶数的时候，每次deque出来一个后，和当前的i值比较，如果小于i，就扔掉，再
deque。
我用abcdefghi 012345678 测试了一下，好象是对的。
不过这种办法很不容易想到，不知道你是怎么想到的？

【在 h**6 的大作中提到】

: 我想了一种办法，不过只适用于二行的情况。
: 假设数组a长度为2n，下标为[0, 2n)
: 显然a[0]不需要交换，我们可以依次寻找[1, 2n)的数需要和哪个数交换即可。
: 循环i于[1, 2n), 假设a[i]与a[k]交换，则一定有k>i
: 当i位于前一半，即[1, n)，定义一个队列，初始为空
: 若i为奇数，k = (i-1)/2+n
: 若i为偶数，k = 队列第一个数并弹出
: 两种情况都需要把k放入队列尾
: 若i位于后一半，即[n, 2n)，销毁队列
: 若i为奇数，k = (i-1)/2+n

a*92010-04-22 07:04

18 楼

完美洗牌问题
存在O(n)时间的in-place算法
http://webhome.cs.uvic.ca/~jellis/perfect.html

i
elemen

【在 Z*****Z 的大作中提到】

: Given a Data Structure having first n integers and next n chars. A = i1 i2 i
: 3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elemen
: ts of the array ass A = i1 c1 i2 c2 ... in cn
: O（nlgn)的算法我知道。有没有O（n)的算法？

K*g2010-04-22 07:04

19 楼

能给个solution的链接吗？

【在 a****9 的大作中提到】

: 完美洗牌问题
: 存在O(n)时间的in-place算法
: http://webhome.cs.uvic.ca/~jellis/perfect.html
:
: i
: elemen

s*d2010-04-22 07:04

20 楼

有人能详细说下divide and conquer的解法吗？举的例子只考虑了数组长度是2^n的情
况。如果divide后出来奇数怎么处理？

m

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

: 1. O(nlogn)
: divide and conquer
: abcd1234 -> ab12cd34 -> a1b2c3d4
: T(n) = O(n) + 2T(n/2) -> O(nlgn)
: 2 O(n)
: This is just like matrix transposition using O(1) space.
: If we use row major, the absolute position for a[i][j] is i*n + j. After
: transposing, it goes to j* m + i = i'*n + j', which in turn will go to j'* m
: + i' and so on. There is a paper on the proof.