CCup题目2.1是不是有更简单的O(n)的解 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

CCup题目2.1是不是有更简单的O(n)的解

CCup题目2.1是不是有更简单的O(n)的解# JobHunting - 待字闺中

c*72013-10-12 07:10

1 楼

今天一个只买过2台的卡就被拒了。还是bb查的松。

f*22013-10-12 07:10

2 楼

2.1 Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an
algorithm to change this array to a1, b1, a2, b2, ..., an, bn
答案给的是O（n*n）和O（nlgn）的解，分治法还得用recursion，这题并没有说不能用
额外的buffer空间，那不可以用最简单的方式弄个O（n）的解吗？
另外像这样的题没说数组类型，是不是面试的时候可以问是哪种类型？
假设是int型，这样写行不行：
int *rearrange(int *arr, int N)
{
if (arr == NULL)
return NULL;

int new_arr[2*N];

for (int i = 0; i < N; i++)
{
new_arr[2*i] = arr[i];
new_arr[2*i+1] = arr[N+i];
}

arr = new_arr;
return arr;
}

D*d2013-10-12 07:10

3 楼

有 O(n) 的算法, 以下是我的解法:
if i in [0 ... n-1], ==> 2*i
if i in [n ... 2n-1], ==> (i-n+1)*2 - 1
从 1 开始把刚替换出来的元素放置在它的新位上，然后根据被替换元素原来的位置计
算新的位置, 记录每个 loop 开始的元素，以免重复调换。 e.g. n = 3, 共 6 个元素
, then
0 --> 0,
1 --> 1 * 2 = 2,
2 --> 2 * 2 = 4,
4 --> (4-3+1)*2-1 = 3
3 --> (3-3+1)*2-1 = 1

an

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

: 2.1 Suppose we have an array a1, a2, ..., an, b1, b2, ..., bn. Implement an
: algorithm to change this array to a1, b1, a2, b2, ..., an, bn
: 答案给的是O（n*n）和O（nlgn）的解，分治法还得用recursion，这题并没有说不能用
: 额外的buffer空间，那不可以用最简单的方式弄个O（n）的解吗？
: 另外像这样的题没说数组类型，是不是面试的时候可以问是哪种类型？
: 假设是int型，这样写行不行：
: int *rearrange(int *arr, int N)
: {
: if (arr == NULL)
: return NULL;

f*22013-10-12 07:10

4 楼

你是指不定义其他数组也有O（n）的解法吗？你的方法也得定义一个新数组吧？

【在 D**********d 的大作中提到】

: 有 O(n) 的算法, 以下是我的解法:
: if i in [0 ... n-1], ==> 2*i
: if i in [n ... 2n-1], ==> (i-n+1)*2 - 1
: 从 1 开始把刚替换出来的元素放置在它的新位上，然后根据被替换元素原来的位置计
: 算新的位置, 记录每个 loop 开始的元素，以免重复调换。 e.g. n = 3, 共 6 个元素
: , then
: 0 --> 0,
: 1 --> 1 * 2 = 2,
: 2 --> 2 * 2 = 4,
: 4 --> (4-3+1)*2-1 = 3

s*r2013-10-12 07:10

5 楼

完美洗牌问题

s*r2013-10-12 07:10

6 楼

有时间 O(N) 空间 O(1) 的解法
这是非常难的问题，远超 Leetcode，如果是很简单的解法，肯定是错的
MS 的员工有论文来讲： A Simple In-Place Algorithm for In-Shuffle

s*u2013-10-12 07:10

7 楼

ccup指的是cc150？第二章不是链表么。。。

l*n2013-10-12 07:10

8 楼

这题很有意思的，总体思路就是存下个位置的值nextVal，把当前位置的值currVal填进
去，然后处理刚才记住的nextVal，如此重复。但是这种重复虽然自身会形成一个环，
整个问题却有多个环。比如下面的例子，1构成一个，2、3、5构成一个，4、6、7构成
一个，8再一个。[1, 2, 4, 8]是每个环的起点。
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 5, 2, 6, 3, 7, 4, 8]
O(n)时间O(1)空间的解法某种意义上就是能算出来每个环的起点。下面是2~34长度的数
组的环的起点，1、2和数组长度自身肯定包含，但是余下的好像很难看出来直接的规律。
[1, 2]
[1, 2, 4]
[1, 2, 6]
[1, 2, 4, 8]
[1, 2, 4, 10]
[1, 2, 12]
[1, 2, 14]
[1, 2, 4, 6, 8, 16]
[1, 2, 4, 18]
[1, 2, 20]
[1, 2, 4, 6, 8, 10, 22]
[1, 2, 6, 24]
[1, 2, 6, 26]
[1, 2, 4, 10, 28]
[1, 2, 30]
[1, 2, 4, 6, 8, 12, 16, 32]
[1, 2, 4, 6, 12, 34]

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

: 有时间 O(N) 空间 O(1) 的解法
: 这是非常难的问题，远超 Leetcode，如果是很简单的解法，肯定是错的
: MS 的员工有论文来讲： A Simple In-Place Algorithm for In-Shuffle