S*******e 发帖数: 379 | 1 假设有一个数组:
a1 a2 a3 a4 .. an b1 b2 b3 b4 .. bn
要变成
a1 b1 a2 b2 a3 b3 a4 b4 .. an bn
要求in place, 比O(n^2)更好的算法。 |
w****x 发帖数: 2483 | |
p*****2 发帖数: 21240 | 3
同跪。等高人。记得讨论过无解是吗?
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 遇到这题直接跪了
|
S*******e 发帖数: 379 | 4 什么意思?直接放弃?
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 遇到这题直接跪了
|
h**********l 发帖数: 6342 | 5 没有吧
这个之前讨论的正数负数分开那个是一样的
【在 S*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设有一个数组: : a1 a2 a3 a4 .. an b1 b2 b3 b4 .. bn : 要变成 : a1 b1 a2 b2 a3 b3 a4 b4 .. an bn : 要求in place, 比O(n^2)更好的算法。
|
v****c 发帖数: 29 | 6 不知道有没有O(n)的算法
O(nlog n)的算法还是很好想的吧
每次花n的时间吧block大小变成一半
【在 S*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设有一个数组: : a1 a2 a3 a4 .. an b1 b2 b3 b4 .. bn : 要变成 : a1 b1 a2 b2 a3 b3 a4 b4 .. an bn : 要求in place, 比O(n^2)更好的算法。
|
w****x 发帖数: 2483 | 7
以前版上讨论过, 后来自己想了两小时无果
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 同跪。等高人。记得讨论过无解是吗?
|
z******t 发帖数: 25 | 8 对于每一个数字,我们是知道shuffle之后的位置的(ai放在2i-1,bi放在2i),比如
a2,应该放在数字第三个位置。
这样就可以设计一个算法:
读取当前的元素,如果它放置位置不对,则把它和占它位置的那个元素替换,直到当前
位置的元素找到为止。
依次对数组每个元素做这个操作直到结束。
因为每次操作就会有一个元素被放到正确的位置上,所以最差情况需要2n-2次操作(假
设数组中有n个a和n个b) |
w****x 发帖数: 2483 | 9
"对于每一个数字,我们是知道shuffle之后的位置的"
谁说的, 要是是这样的:12nfwdfo9r83r92bejrr8172r @$!#
你咋看的出来??
【在 z******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对于每一个数字,我们是知道shuffle之后的位置的(ai放在2i-1,bi放在2i),比如 : a2,应该放在数字第三个位置。 : 这样就可以设计一个算法: : 读取当前的元素,如果它放置位置不对,则把它和占它位置的那个元素替换,直到当前 : 位置的元素找到为止。 : 依次对数组每个元素做这个操作直到结束。 : 因为每次操作就会有一个元素被放到正确的位置上,所以最差情况需要2n-2次操作(假 : 设数组中有n个a和n个b)
|
t**********h 发帖数: 2273 | 10 我觉得他的意思是说前半截a1到an排好序了,后半截b1到bn排好序了,这样来扔。看原
题的描述,似乎是从b1这个数字的下标开始,每个bi依次往ai插
如果是这样的,和我们之前讨论的那个奇数往前扔,偶数往后扔,但是要保持原来的顺
序那道题是不一样
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : "对于每一个数字,我们是知道shuffle之后的位置的" : 谁说的, 要是是这样的:12nfwdfo9r83r92bejrr8172r @$!# : 你咋看的出来??
|
|
|
t**********h 发帖数: 2273 | 11 如果是这样的话,
那么每个ai和bi有一个初始位置,我们知道,题目已给。ai和bi还有一个结束位置,我
们知道,题目已给,那么是可以建立一个初始到结束的映射函数来弄的。
比如从b1开始,它是要占a2的位置的,那么把a2拎起来,存在tmp,然后b1占a2的位置
,然后tmp(这时为a2)找自己的终结位置,找到后,把他拎起来,占位,然后继续下
去。。。。
【在 t**********h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得他的意思是说前半截a1到an排好序了,后半截b1到bn排好序了,这样来扔。看原 : 题的描述,似乎是从b1这个数字的下标开始,每个bi依次往ai插 : 如果是这样的,和我们之前讨论的那个奇数往前扔,偶数往后扔,但是要保持原来的顺 : 序那道题是不一样
|
v****c 发帖数: 29 | 12 问题是这么一轮下去后,你怎么知道哪些已经被放好了,哪些没有放好呢?
就是说下一轮你怎么处理b2?他有可能需要处理有可能不需要处理了
【在 t**********h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果是这样的话, : 那么每个ai和bi有一个初始位置,我们知道,题目已给。ai和bi还有一个结束位置,我 : 们知道,题目已给,那么是可以建立一个初始到结束的映射函数来弄的。 : 比如从b1开始,它是要占a2的位置的,那么把a2拎起来,存在tmp,然后b1占a2的位置 : ,然后tmp(这时为a2)找自己的终结位置,找到后,把他拎起来,占位,然后继续下 : 去。。。。
|
r*****e 发帖数: 792 | 13 从下面的链接看到讨论有很牛的算法,不过一是看懂我估计得花点时间,
而是真要出这题,说出这个答案我想面试的人也会觉得是在背答案,还不如
说那个nlogn的解真实点。
http://zhiqiang.org/blog/science/computer-science/an-algorithm-
http://webhome.cs.uvic.ca/~jellis/perfect.html
【在 S*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设有一个数组: : a1 a2 a3 a4 .. an b1 b2 b3 b4 .. bn : 要变成 : a1 b1 a2 b2 a3 b3 a4 b4 .. an bn : 要求in place, 比O(n^2)更好的算法。
|
w****x 发帖数: 2483 | 14 nlogn怎么解?? 怎么分治, 想不出来, 请教一下 |
r*****e 发帖数: 792 | 15 cup150里面有这道题啊,就是D&C的思想,虽然那个答案看起来
有点不太对劲。我是觉得奇偶的情况好像没有考虑,code自己没写,
觉得太麻烦。做好投降的准备了,呵呵。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : nlogn怎么解?? 怎么分治, 想不出来, 请教一下
|
w****x 发帖数: 2483 | 16
哦,想出来了
a1a2a3a4b1b2b3b4 ==> a1a2b2b1a4a3b3b4 ==> a1a2b1b2 a3a4b3b4
【在 r*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : cup150里面有这道题啊,就是D&C的思想,虽然那个答案看起来 : 有点不太对劲。我是觉得奇偶的情况好像没有考虑,code自己没写, : 觉得太麻烦。做好投降的准备了,呵呵。
|
w****x 发帖数: 2483 | 17 严格来说这样的不算divided & conquer吧, 算conquer then divide |
c****p 发帖数: 6474 | 18 有啊,perfect shuffle
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 同跪。等高人。记得讨论过无解是吗?
|
c****p 发帖数: 6474 | 19 和正负数分开不太一样
【在 h**********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没有吧 : 这个之前讨论的正数负数分开那个是一样的
|
r*****e 发帖数: 792 | 20 中间那步应该是a1a2b1b2a3a4b3b4吧?
也许你这么做也成。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 严格来说这样的不算divided & conquer吧, 算conquer then divide
|
|
|
w****x 发帖数: 2483 | 21
你说的就是我的第3步啊, 两次反转嘛
【在 r*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 中间那步应该是a1a2b1b2a3a4b3b4吧? : 也许你这么做也成。
|
S*******e 发帖数: 379 | 22 展开讲讲?
是说分成4份,交换第二和第三个quarter吗?
如果总长是个奇数呢?
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 你说的就是我的第3步啊, 两次反转嘛
|
w****x 发帖数: 2483 | 23
每个单元反转中段, 再反转中段的两个半段 a1a2a3a4b1b2b3b4 就成了 a1a2b3b2
a3a4b3b4
两个单元, 每个单元再套用这个办法 ,奇数太麻烦了, 我估计就放弃了
【在 S*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 展开讲讲? : 是说分成4份,交换第二和第三个quarter吗? : 如果总长是个奇数呢?
|
q****x 发帖数: 7404 | 24 置换群?
【在 S*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设有一个数组: : a1 a2 a3 a4 .. an b1 b2 b3 b4 .. bn : 要变成 : a1 b1 a2 b2 a3 b3 a4 b4 .. an bn : 要求in place, 比O(n^2)更好的算法。
|
r*****e 发帖数: 792 | 25 我也是觉得奇数时太麻烦所以没写成code,就打算口述思想了,呵呵。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 每个单元反转中段, 再反转中段的两个半段 a1a2a3a4b1b2b3b4 就成了 a1a2b3b2 : a3a4b3b4 : 两个单元, 每个单元再套用这个办法 ,奇数太麻烦了, 我估计就放弃了
|
p*****o 发帖数: 1285 | 26 这个方法类似于那个给一个序列找第一个缺少的正数一样。但有一个假定是可以根据数
字本身确定它的最终位置, 对这个题似乎不成立。
【在 z******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对于每一个数字,我们是知道shuffle之后的位置的(ai放在2i-1,bi放在2i),比如 : a2,应该放在数字第三个位置。 : 这样就可以设计一个算法: : 读取当前的元素,如果它放置位置不对,则把它和占它位置的那个元素替换,直到当前 : 位置的元素找到为止。 : 依次对数组每个元素做这个操作直到结束。 : 因为每次操作就会有一个元素被放到正确的位置上,所以最差情况需要2n-2次操作(假 : 设数组中有n个a和n个b)
|
t**********h 发帖数: 2273 | 27 大牛们,多多讨论,最近忙着面试,回来学习你们最终定论 |
f*********i 发帖数: 197 | 28 The following is an O(nlgn) solution, I hope that helps
// start is initially 0, end = aabb.length-1
public static char[] changeOrderOfString(char[] aabb, int start, int
end)
{
if (end - start <= 1)
return aabb;
if ((end - start + 1) % 4 != 0)
{
for (int i = start + 1, j = end - 1; j > i; j--, i++)
{
char temp = aabb[i];
aabb[i] = aabb[j];
aabb[j] = temp;
}
return changeOrderOfString(aabb, start + 1, end - 1);
}
else
{
int mid = (start + end) / 2;
int frondMid = (start + mid) / 2 + 1, backMid = (mid + end)
/ 2;
for (int i = 0; frondMid + i <= mid; i++)
{
char temp = aabb[frondMid + i];
aabb[frondMid + i] = aabb[mid + 1 + i];
aabb[mid + 1 + i] = temp;
}
aabb = changeOrderOfString(aabb, start, mid);
aabb = changeOrderOfString(aabb, mid + 1, end);
return aabb;
}
} |
s****e 发帖数: 638 | 29 下面这个是O(n) 不知道这样做行不行。
#include
#include
#include
using namespace std;
void shuffle(char* A)
{
int size = strlen(A);
int i=1;
while(i
if (A[i] & 0x80) {
i++;
continue;
}
int j=i;
int j2;
while(true){
if ( j < size/2 ) j2 = j*2;
else j2 = 2*(j-size/2)+1;
if (j2<=i) break;
swap(A[i], A[j2]);
A[j2] |= 0x80;
j=j2;
}
i++;
}
for (int i=0; i
}
int main(){
vector strVec;
strVec.push_back("Aa");
strVec.push_back("ABab");
strVec.push_back("ABCabc");
strVec.push_back("ABCDabcd");
strVec.push_back("ABCDEabcde");
strVec.push_back("ABCDEFabcdef");
strVec.push_back("ABCDEFGabcdefg");
strVec.push_back("ABCDEFGHabcdefgh");
strVec.push_back("ABCDEFGHIabcdefghi");
strVec.push_back("ABCDEFGHIJabcdefghij");
for (int i=0; i
char* A = strVec.at(i);
shuffle(A);
cout<
}
return 0;
}
--------------------------
Aa
AaBb
AaBbCc
AaBbCcDd
AaBbCcDdEe
AaBbCcDdEeFf
AaBbCcDdEeFfGg
AaBbCcDdEeFfGgHh
AaBbCcDdEeFfGgHhIi
AaBbCcDdEeFfGgHhIiJj
【在 S*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设有一个数组: : a1 a2 a3 a4 .. an b1 b2 b3 b4 .. bn : 要变成 : a1 b1 a2 b2 a3 b3 a4 b4 .. an bn : 要求in place, 比O(n^2)更好的算法。
|
t****t 发帖数: 6806 | 30 偷一位当存储不能算原地.
【在 s****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 下面这个是O(n) 不知道这样做行不行。 : #include : #include : #include : using namespace std; : void shuffle(char* A) : { : int size = strlen(A); : int i=1; : while(i
|
|
|
s****e 发帖数: 638 | 31 没有违反下面说法啊? 怎么定义in-place?
http://en.wikipedia.org/wiki/In-place_algorithm
In computer science, an in-place algorithm (or in Latin in situ) is an
algorithm which transforms input using a data structure with a small,
constant amount of extra storage space. The input is usually overwritten
by
the output as the algorithm executes.
【在 t****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 偷一位当存储不能算原地.
|
t****t 发帖数: 6806 | 32 you assume the original data is readable char which is 7-bit saved in 8-bit.
however this is not necessary true. same can be said if you assume all
input are positive and you use the sign bit as temporary space.
【在 s****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没有违反下面说法啊? 怎么定义in-place? : http://en.wikipedia.org/wiki/In-place_algorithm : In computer science, an in-place algorithm (or in Latin in situ) is an : algorithm which transforms input using a data structure with a small, : constant amount of extra storage space. The input is usually overwritten : by : the output as the algorithm executes.
|
s****e 发帖数: 638 | 33 yeah,that's a problem.
bit.
【在 t****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : you assume the original data is readable char which is 7-bit saved in 8-bit. : however this is not necessary true. same can be said if you assume all : input are positive and you use the sign bit as temporary space.
|
r*****e 发帖数: 792 | 34 其实奇偶是一个意思,不用分开考虑。
第一次反转是半个现在partition的长度,
第二次就是前面不动部分的长度,
第三次就是后面不动部分的长度。
终于写了一下这个的code,算是nlogn的解法搞定了。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 每个单元反转中段, 再反转中段的两个半段 a1a2a3a4b1b2b3b4 就成了 a1a2b3b2 : a3a4b3b4 : 两个单元, 每个单元再套用这个办法 ,奇数太麻烦了, 我估计就放弃了
|
X*K 发帖数: 87 | 35 前几天看了发现换来换去的没概念,撂在一边。今天一看,不就是个排序的问题吗。把
数字做primary key,ab做secondary key,那heap sort和quick sort这些in-place的
都可以啊,O(NlogN)。
O(n) in-place是不可能的,不然merge sort就可以in-place了。相当于把前后两个
sorted array merge
【在 S*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设有一个数组: : a1 a2 a3 a4 .. an b1 b2 b3 b4 .. bn : 要变成 : a1 b1 a2 b2 a3 b3 a4 b4 .. an bn : 要求in place, 比O(n^2)更好的算法。
|
h*******e 发帖数: 225 | 36
先看看回帖再下结论,不要那么想当然
【在 X*K 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 前几天看了发现换来换去的没概念,撂在一边。今天一看,不就是个排序的问题吗。把 : 数字做primary key,ab做secondary key,那heap sort和quick sort这些in-place的 : 都可以啊,O(NlogN)。 : O(n) in-place是不可能的,不然merge sort就可以in-place了。相当于把前后两个 : sorted array merge
|
d**********x 发帖数: 4083 | 37 恩。。用某种数学方法是可以O(n)的
我问过acm牛人。。
【在 q****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 置换群?
|
X*K 发帖数: 87 | 38 怎么是想当然呢,你给个in-place O(n)的算法,那么同样那可以用来
把两个排好序的数组in-place归并,那恭喜你,你找到了in-place的
merge sort算法,牛大了。
【在 h*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 先看看回帖再下结论,不要那么想当然
|
X*K 发帖数: 87 | 39 OK不对,这题应该是归并两个排好序数组的特例,希望能看到O(N)的方法。
【在 X*K 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 怎么是想当然呢,你给个in-place O(n)的算法,那么同样那可以用来 : 把两个排好序的数组in-place归并,那恭喜你,你找到了in-place的 : merge sort算法,牛大了。
|
H****r 发帖数: 2801 | 40 这篇paper:
http://arxiv.org/pdf/0805.1598v1.pdf
【在 S*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设有一个数组: : a1 a2 a3 a4 .. an b1 b2 b3 b4 .. bn : 要变成 : a1 b1 a2 b2 a3 b3 a4 b4 .. an bn : 要求in place, 比O(n^2)更好的算法。
|
|
|
C***U 发帖数: 2406 | 41 应该是用置换群的理论
这个mod的函数其实就是一个2n->2n的置换么
把这个permutation拆成cycles以后
把每个cycle都做一遍变换
就是把这个cycle里面的元素都放到了合适的位置
所有cycle都走遍的时候就完成了shuffle
时间上就是O(n)了
【在 d**********x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 恩。。用某种数学方法是可以O(n)的 : 我问过acm牛人。。
|
g**x 发帖数: 373 | 42 Agree. How to get those cycles in O(1) space?
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是用置换群的理论 : 这个mod的函数其实就是一个2n->2n的置换么 : 把这个permutation拆成cycles以后 : 把每个cycle都做一遍变换 : 就是把这个cycle里面的元素都放到了合适的位置 : 所有cycle都走遍的时候就完成了shuffle : 时间上就是O(n)了
|
g**x 发帖数: 373 | 43 In this article, http://webhome.cs.uvic.ca/~jellis/perfect.html
The requirement of in-place space seems to be reduced to O(log N) space. It
is not hard to use a bit map to identify circles.
【在 g**x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Agree. How to get those cycles in O(1) space?
|