f*****2
发帖数: 141 | 1 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**********d
发帖数: 849 | 2 有 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*****2
发帖数: 141 | 3 你是指不定义其他数组也有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*****r
发帖数: 108 | | s*****r
发帖数: 108 | 5 有时间 O(N) 空间 O(1) 的解法
这是非常难的问题，远超 Leetcode，如果是很简单的解法，肯定是错的
MS 的员工有论文来讲： A Simple In-Place Algorithm for In-Shuffle | s********u
发帖数: 1109 | 6 ccup指的是cc150？第二章不是链表么。。。 | l*n
发帖数: 529 | 7 这题很有意思的，总体思路就是存下个位置的值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
| T******e
发帖数: 157 | 8 我对你的代码有疑问，你生成的new_arr是分配在stack上的，这样当函数结束的时候这
个区域就要被删除了，返回的指针指向的区域是非法的。你这段代码通过测试了吗？ |
|
