一道老题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道老题

一道老题# JobHunting - 待字闺中

m*n2015-03-07 08:03

1 楼

昨天被问了一道老题. array={a1, a2, ..., an, b1, b2, ..., bn}变成 {a1,bn,a2,
bn-1,...,bn,a0},要求时间复杂度O(N),空间O(1).
当时根本不会,我所知道最快的算法是类似quick sort的方法,要O(NlogN), 这个O(N)怎
么做? 我记得以前有人贴过,找不到了.
还有不用random, time种子什么的, 怎么给shuffle任意一个数组,
大概就是
void shuffle(int A[]){
}
每次出来的 A 的结果不一样.

h*k2015-03-07 08:03

2 楼

第一题应该是完美洗牌算法。。O(N) time O(1) space的解法比较难懂感觉
http://www.meetqun.com/thread-2461-1-1.html

C*t2015-03-07 08:03

3 楼

There are 2 ways to do these.
|--A1--|---A2---|---B1---B2---|
Evenly divide An and Bn into (A1,A2), (B1,B2) respectively.
len(A2) - len(A1) = len(B2) - len(B1) == 1 or 0 depends on odd or even.
Method 1: O(n*logn)
1a. Exchange A2 and B1.
1B. recursively do this on two new subarrays A1+B1, A2+B2
Method 2 : O(n)
2a. The idea is the same as Method 1. Now for each index from 0 to 2*n-1, we
have 4 different domains A1, A2, B1, B2.
2b. Map index of A1 to even index of 2*len(A1)
Map index of B1 to odd index of 2*len(A1)
Map index of A2 to 2*(n//4) + even index of 2*len(A2)
Map index of B2 to 2*(n//4) + odd index of 2*len(A2)

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

: 昨天被问了一道老题. array={a1, a2, ..., an, b1, b2, ..., bn}变成 {a1,bn,a2,
: bn-1,...,bn,a0},要求时间复杂度O(N),空间O(1).
: 当时根本不会,我所知道最快的算法是类似quick sort的方法,要O(NlogN), 这个O(N)怎
: 么做? 我记得以前有人贴过,找不到了.
: 还有不用random, time种子什么的, 怎么给shuffle任意一个数组,
: 大概就是
: void shuffle(int A[]){
: }
: 每次出来的 A 的结果不一样.

h*k2015-03-07 08:03

4 楼

你这空间不是O(1)吧

we

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

: There are 2 ways to do these.
: |--A1--|---A2---|---B1---B2---|
: Evenly divide An and Bn into (A1,A2), (B1,B2) respectively.
: len(A2) - len(A1) = len(B2) - len(B1) == 1 or 0 depends on odd or even.
: Method 1: O(n*logn)
: 1a. Exchange A2 and B1.
: 1B. recursively do this on two new subarrays A1+B1, A2+B2
: Method 2 : O(n)
: 2a. The idea is the same as Method 1. Now for each index from 0 to 2*n-1, we
: have 4 different domains A1, A2, B1, B2.

C*t2015-03-07 08:03

5 楼

Method 1 uses rotation algorithm where no extra space is needed.
Method 2 just does multiple swaps at the same time. No extra space.

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

: 你这空间不是O(1)吧
:
: we

C*t2015-03-07 08:03

6 楼

Q1.
def swap(nums):
n = len(nums)
for i in range(n):
tmp = origIdx(i, n//2)
while tmp < i: tmp = origIdx(tmp, n//2)
nums[i], nums[tmp] = nums[tmp], nums[i]
print(nums)
def origIdx(cur, n):
return (cur%2)*n + cur//2