MS a0, a1, ..., b0, b1... 问题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

MS a0, a1, ..., b0, b1... 问题

MS a0, a1, ..., b0, b1... 问题# JobHunting - 待字闺中

l*r2013-12-06 08:12

1 楼

Input:
[a1,a2,a3...,an,b1,b2...bn]
Output: [a1,b1,a2,b2.....an,bn] , solution should be in-place.
除了N*N，还有更好的办法不？

v*a2013-12-06 08:12

2 楼

http://www.geeksforgeeks.org/an-in-place-algorithm-for-string-t

s*x2013-12-06 08:12

3 楼

这个办法很不好记，3^k+1, I+= 3?

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

: http://www.geeksforgeeks.org/an-in-place-algorithm-for-string-t

x*42013-12-06 08:12

4 楼

http://www.mitbbs.com/article_t/JobHunting/32568289.html
Microsoft 4.1

w*e2013-12-06 08:12

5 楼

我觉得可以用leetcode里面missingfirstpositive差不多的解法，
比如你有array 12345678 要变成 15263748
int getIndex(int i){
if (i > n) return (2*(i-n) - 1);
else return (i*2 - 2);
}
for (int i = 0; i < 2*n; i++){
while (getIndex(array[i]) != i)
swap(array[i], array[getIndex(array[i]]);
}
index: 01234567
12345678
132..
15243...
15273648
15263748 done

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

: Input:
: [a1,a2,a3...,an,b1,b2...bn]
: Output: [a1,b1,a2,b2.....an,bn] , solution should be in-place.
: 除了N*N，还有更好的办法不？

l*n2013-12-06 08:12

6 楼

类似，但是有区别。first missing positive里面可以简单跳过一些element，但是本
题如果出现“环”之后，没有办法判断下一个element是否被rearrange过，所以会需要
额外的空间进行标记才行。

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

:
: 我觉得可以用leetcode里面missingfirstpositive差不多的解法，
: 比如你有array 12345678 要变成 15263748
: int getIndex(int i){
: if (i > n) return (2*(i-n) - 1);
: else return (i*2 - 2);
: }
: for (int i = 0; i < 2*n; i++){
: while (getIndex(array[i]) != i)
: swap(array[i], array[getIndex(array[i]]);

b*e2013-12-06 08:12

7 楼

其实是考虑函数
x_i+1 = (2*x_i) % (n-1)
当n even, 每个element x_i 会移到 element x_i+1。
而当 n = 3^k + 1的时候这个函数能遍历所有1...n-2. 所以换一圈后就搞定了。当 n!
=3^k+1的时候，可以分段先搞定一段，然后下一段。
现场考这题基本就挂了。

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

: http://www.geeksforgeeks.org/an-in-place-algorithm-for-string-t

v*a2013-12-06 08:12

8 楼

这个没错，但是复杂度是n*n 吧。这道题要求in-place 又是linear的确就难了。。

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

s*x2013-12-06 08:12

9 楼

nlogn 应该就可以了, code 很好写， recursion，
abcde12345 to abc321 ed45 to abc123de45
，then recursively do abc123 and de45

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

: 这个没错，但是复杂度是n*n 吧。这道题要求in-place 又是linear的确就难了。。