传说南方孩子说不了这个:# Joke - 肚皮舞运动
S*e
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)更好的算法。
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*7
2 楼
蓝教练是女教练，吕教练是男教练。蓝教练不是男教练，吕教练不是女教练。蓝南是男
篮主力，吕楠是女篮主力。吕教练在男篮训练蓝南，蓝教练在女篮训练吕楠。
篮主力，吕楠是女篮主力。吕教练在男篮训练蓝南，蓝教练在女篮训练吕楠。
w*x
3 楼
遇到这题直接跪了
s*m
4 楼
南方的孩子每问题
“蓝”方的孩子有问题
【在 c*******7 的大作中提到】
: 蓝教练是女教练，吕教练是男教练。蓝教练不是男教练，吕教练不是女教练。蓝南是男
: 篮主力，吕楠是女篮主力。吕教练在男篮训练蓝南，蓝教练在女篮训练吕楠。
“蓝”方的孩子有问题
【在 c*******7 的大作中提到】
: 蓝教练是女教练，吕教练是男教练。蓝教练不是男教练，吕教练不是女教练。蓝南是男
: 篮主力，吕楠是女篮主力。吕教练在男篮训练蓝南，蓝教练在女篮训练吕楠。
p*2
5 楼
同跪。等高人。记得讨论过无解是吗？
【在 w****x 的大作中提到】
: 遇到这题直接跪了
g*n
6 楼
校运会女播音员: 下面的比赛是篮子一百米和驴子一百米。
【在 c*******7 的大作中提到】
: 蓝教练是女教练，吕教练是男教练。蓝教练不是男教练，吕教练不是女教练。蓝南是男
: 篮主力，吕楠是女篮主力。吕教练在男篮训练蓝南，蓝教练在女篮训练吕楠。
【在 c*******7 的大作中提到】
: 蓝教练是女教练，吕教练是男教练。蓝教练不是男教练，吕教练不是女教练。蓝南是男
: 篮主力，吕楠是女篮主力。吕教练在男篮训练蓝南，蓝教练在女篮训练吕楠。
S*e
7 楼
什么意思？直接放弃？
【在 w****x 的大作中提到】
: 遇到这题直接跪了
【在 w****x 的大作中提到】
: 遇到这题直接跪了
p*p
8 楼
俺能说，看来俺不属于南方
h*l
9 楼
没有吧
这个之前讨论的正数负数分开那个是一样的
【在 S*******e 的大作中提到】
: 假设有一个数组：
: 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)更好的算法。
这个之前讨论的正数负数分开那个是一样的
【在 S*******e 的大作中提到】
: 假设有一个数组：
: 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)更好的算法。
i*a
10 楼
this always kick my ass... not sure which is "L" which is "N"
南方男子篮球队
【在 c*******7 的大作中提到】
: 蓝教练是女教练，吕教练是男教练。蓝教练不是男教练，吕教练不是女教练。蓝南是男
: 篮主力，吕楠是女篮主力。吕教练在男篮训练蓝南，蓝教练在女篮训练吕楠。
南方男子篮球队
【在 c*******7 的大作中提到】
: 蓝教练是女教练，吕教练是男教练。蓝教练不是男教练，吕教练不是女教练。蓝南是男
: 篮主力，吕楠是女篮主力。吕教练在男篮训练蓝南，蓝教练在女篮训练吕楠。
v*c
11 楼
不知道有没有O(n)的算法
O(nlog n)的算法还是很好想的吧
每次花n的时间吧block大小变成一半
【在 S*******e 的大作中提到】
: 假设有一个数组：
: 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)更好的算法。
O(nlog n)的算法还是很好想的吧
每次花n的时间吧block大小变成一半
【在 S*******e 的大作中提到】
: 假设有一个数组：
: 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)更好的算法。
e*t
12 楼
南方某方言表示毫无压力
蓝：lam
男：nam
吕：lu
女：ni
【在 c*******7 的大作中提到】
: 蓝教练是女教练，吕教练是男教练。蓝教练不是男教练，吕教练不是女教练。蓝南是男
: 篮主力，吕楠是女篮主力。吕教练在男篮训练蓝南，蓝教练在女篮训练吕楠。
蓝：lam
男：nam
吕：lu
女：ni
【在 c*******7 的大作中提到】
: 蓝教练是女教练，吕教练是男教练。蓝教练不是男教练，吕教练不是女教练。蓝南是男
: 篮主力，吕楠是女篮主力。吕教练在男篮训练蓝南，蓝教练在女篮训练吕楠。
w*x
13 楼
以前版上讨论过, 后来自己想了两小时无果
【在 p*****2 的大作中提到】
:
: 同跪。等高人。记得讨论过无解是吗？
s*x
14 楼
欧式北方因， 怎么也说着特费劲？
z*t
15 楼
对于每一个数字，我们是知道shuffle之后的位置的（ai放在2i-1，bi放在2i），比如
a2,应该放在数字第三个位置。
这样就可以设计一个算法：
读取当前的元素，如果它放置位置不对，则把它和占它位置的那个元素替换，直到当前
位置的元素找到为止。
依次对数组每个元素做这个操作直到结束。
因为每次操作就会有一个元素被放到正确的位置上，所以最差情况需要2n-2次操作（假
设数组中有n个a和n个b）
a2,应该放在数字第三个位置。
这样就可以设计一个算法：
读取当前的元素，如果它放置位置不对，则把它和占它位置的那个元素替换，直到当前
位置的元素找到为止。
依次对数组每个元素做这个操作直到结束。
因为每次操作就会有一个元素被放到正确的位置上，所以最差情况需要2n-2次操作（假
设数组中有n个a和n个b）
c*7
16 楼
啊，我发这个帖子是不是有点mean啊：（
w*x
17 楼
"对于每一个数字，我们是知道shuffle之后的位置的"
谁说的, 要是是这样的:12nfwdfo9r83r92bejrr8172r @$!#
你咋看的出来??
【在 z******t 的大作中提到】
: 对于每一个数字，我们是知道shuffle之后的位置的（ai放在2i-1，bi放在2i），比如
: a2,应该放在数字第三个位置。
: 这样就可以设计一个算法：
: 读取当前的元素，如果它放置位置不对，则把它和占它位置的那个元素替换，直到当前
: 位置的元素找到为止。
: 依次对数组每个元素做这个操作直到结束。
: 因为每次操作就会有一个元素被放到正确的位置上，所以最差情况需要2n-2次操作（假
: 设数组中有n个a和n个b）
s*a
18 楼
我是南方的，说起来很yong易啊
【在 s**x 的大作中提到】
: 欧式北方因， 怎么也说着特费劲？
【在 s**x 的大作中提到】
: 欧式北方因， 怎么也说着特费劲？
t*h
19 楼
我觉得他的意思是说前半截a1到an排好序了，后半截b1到bn排好序了，这样来扔。看原
题的描述，似乎是从b1这个数字的下标开始，每个bi依次往ai插
如果是这样的，和我们之前讨论的那个奇数往前扔，偶数往后扔，但是要保持原来的顺
序那道题是不一样
【在 w****x 的大作中提到】
:
: "对于每一个数字，我们是知道shuffle之后的位置的"
: 谁说的, 要是是这样的:12nfwdfo9r83r92bejrr8172r @$!#
: 你咋看的出来??
题的描述，似乎是从b1这个数字的下标开始，每个bi依次往ai插
如果是这样的，和我们之前讨论的那个奇数往前扔，偶数往后扔，但是要保持原来的顺
序那道题是不一样
【在 w****x 的大作中提到】
:
: "对于每一个数字，我们是知道shuffle之后的位置的"
: 谁说的, 要是是这样的:12nfwdfo9r83r92bejrr8172r @$!#
: 你咋看的出来??
x*g
20 楼
安徽人？
【在 s*******a 的大作中提到】
: 我是南方的，说起来很yong易啊
【在 s*******a 的大作中提到】
: 我是南方的，说起来很yong易啊
t*h
21 楼
如果是这样的话，
那么每个ai和bi有一个初始位置，我们知道，题目已给。ai和bi还有一个结束位置，我
们知道，题目已给，那么是可以建立一个初始到结束的映射函数来弄的。
比如从b1开始，它是要占a2的位置的，那么把a2拎起来，存在tmp，然后b1占a2的位置
，然后tmp（这时为a2）找自己的终结位置，找到后，把他拎起来，占位，然后继续下
去。。。。
【在 t**********h 的大作中提到】
: 我觉得他的意思是说前半截a1到an排好序了，后半截b1到bn排好序了，这样来扔。看原
: 题的描述，似乎是从b1这个数字的下标开始，每个bi依次往ai插
: 如果是这样的，和我们之前讨论的那个奇数往前扔，偶数往后扔，但是要保持原来的顺
: 序那道题是不一样
那么每个ai和bi有一个初始位置，我们知道，题目已给。ai和bi还有一个结束位置，我
们知道，题目已给，那么是可以建立一个初始到结束的映射函数来弄的。
比如从b1开始，它是要占a2的位置的，那么把a2拎起来，存在tmp，然后b1占a2的位置
，然后tmp（这时为a2）找自己的终结位置，找到后，把他拎起来，占位，然后继续下
去。。。。
【在 t**********h 的大作中提到】
: 我觉得他的意思是说前半截a1到an排好序了，后半截b1到bn排好序了，这样来扔。看原
: 题的描述，似乎是从b1这个数字的下标开始，每个bi依次往ai插
: 如果是这样的，和我们之前讨论的那个奇数往前扔，偶数往后扔，但是要保持原来的顺
: 序那道题是不一样
v*c
22 楼
问题是这么一轮下去后，你怎么知道哪些已经被放好了，哪些没有放好呢？
就是说下一轮你怎么处理b2？他有可能需要处理有可能不需要处理了
【在 t**********h 的大作中提到】
: 如果是这样的话，
: 那么每个ai和bi有一个初始位置，我们知道，题目已给。ai和bi还有一个结束位置，我
: 们知道，题目已给，那么是可以建立一个初始到结束的映射函数来弄的。
: 比如从b1开始，它是要占a2的位置的，那么把a2拎起来，存在tmp，然后b1占a2的位置
: ，然后tmp（这时为a2）找自己的终结位置，找到后，把他拎起来，占位，然后继续下
: 去。。。。
就是说下一轮你怎么处理b2？他有可能需要处理有可能不需要处理了
【在 t**********h 的大作中提到】
: 如果是这样的话，
: 那么每个ai和bi有一个初始位置，我们知道，题目已给。ai和bi还有一个结束位置，我
: 们知道，题目已给，那么是可以建立一个初始到结束的映射函数来弄的。
: 比如从b1开始，它是要占a2的位置的，那么把a2拎起来，存在tmp，然后b1占a2的位置
: ，然后tmp（这时为a2）找自己的终结位置，找到后，把他拎起来，占位，然后继续下
: 去。。。。
r*e
23 楼
从下面的链接看到讨论有很牛的算法，不过一是看懂我估计得花点时间，
而是真要出这题，说出这个答案我想面试的人也会觉得是在背答案，还不如
说那个nlogn的解真实点。
http://zhiqiang.org/blog/science/computer-science/an-algorithm-
http://webhome.cs.uvic.ca/~jellis/perfect.html
【在 S*******e 的大作中提到】
: 假设有一个数组：
: 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)更好的算法。
而是真要出这题，说出这个答案我想面试的人也会觉得是在背答案，还不如
说那个nlogn的解真实点。
http://zhiqiang.org/blog/science/computer-science/an-algorithm-
http://webhome.cs.uvic.ca/~jellis/perfect.html
【在 S*******e 的大作中提到】
: 假设有一个数组：
: 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
24 楼
nlogn怎么解?? 怎么分治, 想不出来, 请教一下
r*e
25 楼
cup150里面有这道题啊，就是D&C的思想，虽然那个答案看起来
有点不太对劲。我是觉得奇偶的情况好像没有考虑，code自己没写，
觉得太麻烦。做好投降的准备了，呵呵。
【在 w****x 的大作中提到】
: nlogn怎么解?? 怎么分治, 想不出来, 请教一下
有点不太对劲。我是觉得奇偶的情况好像没有考虑，code自己没写，
觉得太麻烦。做好投降的准备了，呵呵。
【在 w****x 的大作中提到】
: nlogn怎么解?? 怎么分治, 想不出来, 请教一下
w*x
26 楼
哦,想出来了
a1a2a3a4b1b2b3b4 ==> a1a2b2b1a4a3b3b4 ==> a1a2b1b2 a3a4b3b4
【在 r*****e 的大作中提到】
: cup150里面有这道题啊，就是D&C的思想，虽然那个答案看起来
: 有点不太对劲。我是觉得奇偶的情况好像没有考虑，code自己没写，
: 觉得太麻烦。做好投降的准备了，呵呵。
w*x
27 楼
严格来说这样的不算divided & conquer吧, 算conquer then divide
c*p
28 楼
有啊，perfect shuffle
【在 p*****2 的大作中提到】
:
: 同跪。等高人。记得讨论过无解是吗？
【在 p*****2 的大作中提到】
:
: 同跪。等高人。记得讨论过无解是吗？
c*p
29 楼
和正负数分开不太一样
【在 h**********l 的大作中提到】
: 没有吧
: 这个之前讨论的正数负数分开那个是一样的
【在 h**********l 的大作中提到】
: 没有吧
: 这个之前讨论的正数负数分开那个是一样的
r*e
30 楼
中间那步应该是a1a2b1b2a3a4b3b4吧？
也许你这么做也成。
【在 w****x 的大作中提到】
: 严格来说这样的不算divided & conquer吧, 算conquer then divide
也许你这么做也成。
【在 w****x 的大作中提到】
: 严格来说这样的不算divided & conquer吧, 算conquer then divide
w*x
31 楼
你说的就是我的第3步啊, 两次反转嘛
【在 r*****e 的大作中提到】
: 中间那步应该是a1a2b1b2a3a4b3b4吧？
: 也许你这么做也成。
S*e
32 楼
展开讲讲？
是说分成4份，交换第二和第三个quarter吗？
如果总长是个奇数呢？
【在 w****x 的大作中提到】
:
: 你说的就是我的第3步啊, 两次反转嘛
是说分成4份，交换第二和第三个quarter吗？
如果总长是个奇数呢？
【在 w****x 的大作中提到】
:
: 你说的就是我的第3步啊, 两次反转嘛
w*x
33 楼
每个单元反转中段, 再反转中段的两个半段 a1a2a3a4b1b2b3b4 就成了 a1a2b3b2
a3a4b3b4
两个单元, 每个单元再套用这个办法 ,奇数太麻烦了, 我估计就放弃了
【在 S*******e 的大作中提到】
: 展开讲讲？
: 是说分成4份，交换第二和第三个quarter吗？
: 如果总长是个奇数呢？
q*x
34 楼
置换群？
【在 S*******e 的大作中提到】
: 假设有一个数组：
: 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)更好的算法。
【在 S*******e 的大作中提到】
: 假设有一个数组：
: 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
35 楼
我也是觉得奇数时太麻烦所以没写成code，就打算口述思想了，呵呵。
【在 w****x 的大作中提到】
:
: 每个单元反转中段, 再反转中段的两个半段 a1a2a3a4b1b2b3b4 就成了 a1a2b3b2
: a3a4b3b4
: 两个单元, 每个单元再套用这个办法 ,奇数太麻烦了, 我估计就放弃了
【在 w****x 的大作中提到】
:
: 每个单元反转中段, 再反转中段的两个半段 a1a2a3a4b1b2b3b4 就成了 a1a2b3b2
: a3a4b3b4
: 两个单元, 每个单元再套用这个办法 ,奇数太麻烦了, 我估计就放弃了
p*o
36 楼
这个方法类似于那个给一个序列找第一个缺少的正数一样。但有一个假定是可以根据数
字本身确定它的最终位置， 对这个题似乎不成立。
【在 z******t 的大作中提到】
: 对于每一个数字，我们是知道shuffle之后的位置的（ai放在2i-1，bi放在2i），比如
: a2,应该放在数字第三个位置。
: 这样就可以设计一个算法：
: 读取当前的元素，如果它放置位置不对，则把它和占它位置的那个元素替换，直到当前
: 位置的元素找到为止。
: 依次对数组每个元素做这个操作直到结束。
: 因为每次操作就会有一个元素被放到正确的位置上，所以最差情况需要2n-2次操作（假
: 设数组中有n个a和n个b）
字本身确定它的最终位置， 对这个题似乎不成立。
【在 z******t 的大作中提到】
: 对于每一个数字，我们是知道shuffle之后的位置的（ai放在2i-1，bi放在2i），比如
: a2,应该放在数字第三个位置。
: 这样就可以设计一个算法：
: 读取当前的元素，如果它放置位置不对，则把它和占它位置的那个元素替换，直到当前
: 位置的元素找到为止。
: 依次对数组每个元素做这个操作直到结束。
: 因为每次操作就会有一个元素被放到正确的位置上，所以最差情况需要2n-2次操作（假
: 设数组中有n个a和n个b）
t*h
37 楼
大牛们，多多讨论，最近忙着面试，回来学习你们最终定论
f*i
38 楼
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;
}
}
// 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
39 楼
下面这个是O(n) 不知道这样做行不行。
#include
#include
#include
using namespace std;
void shuffle(char* A)
{
int size = strlen(A);
int i=1;
while(i
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
shuffle(A);
cout<}
return 0;
}
--------------------------
Aa
AaBb
AaBbCc
AaBbCcDd
AaBbCcDdEe
AaBbCcDdEeFf
AaBbCcDdEeFfGg
AaBbCcDdEeFfGgHh
AaBbCcDdEeFfGgHhIi
AaBbCcDdEeFfGgHhIiJj
【在 S*******e 的大作中提到】
: 假设有一个数组：
: 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)更好的算法。
#include
#include
#include
using namespace std;
void shuffle(char* A)
{
int size = strlen(A);
int i=1;
while(i
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.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
shuffle(A);
cout<}
return 0;
}
--------------------------
Aa
AaBb
AaBbCc
AaBbCcDd
AaBbCcDdEe
AaBbCcDdEeFf
AaBbCcDdEeFfGg
AaBbCcDdEeFfGgHh
AaBbCcDdEeFfGgHhIi
AaBbCcDdEeFfGgHhIiJj
【在 S*******e 的大作中提到】
: 假设有一个数组：
: 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
40 楼
偷一位当存储不能算原地.
【在 s****e 的大作中提到】
: 下面这个是O(n) 不知道这样做行不行。
: #include
: #include
: #include
: using namespace std;
: void shuffle(char* A)
: {
: int size = strlen(A);
: int i=1;
: while(i
【在 s****e 的大作中提到】
: 下面这个是O(n) 不知道这样做行不行。
: #include
: #include
: #include
: using namespace std;
: void shuffle(char* A)
: {
: int size = strlen(A);
: int i=1;
: while(i
s*e
41 楼
没有违反下面说法啊？ 怎么定义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 的大作中提到】
: 偷一位当存储不能算原地.
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 的大作中提到】
: 偷一位当存储不能算原地.
t*t
42 楼
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 的大作中提到】
: 没有违反下面说法啊？ 怎么定义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.
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 的大作中提到】
: 没有违反下面说法啊？ 怎么定义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
43 楼
yeah,that's a problem.
bit.
【在 t****t 的大作中提到】
: 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.
bit.
【在 t****t 的大作中提到】
: 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
44 楼
其实奇偶是一个意思，不用分开考虑。
第一次反转是半个现在partition的长度，
第二次就是前面不动部分的长度，
第三次就是后面不动部分的长度。
终于写了一下这个的code，算是nlogn的解法搞定了。
【在 w****x 的大作中提到】
:
: 每个单元反转中段, 再反转中段的两个半段 a1a2a3a4b1b2b3b4 就成了 a1a2b3b2
: a3a4b3b4
: 两个单元, 每个单元再套用这个办法 ,奇数太麻烦了, 我估计就放弃了
第一次反转是半个现在partition的长度，
第二次就是前面不动部分的长度，
第三次就是后面不动部分的长度。
终于写了一下这个的code，算是nlogn的解法搞定了。
【在 w****x 的大作中提到】
:
: 每个单元反转中段, 再反转中段的两个半段 a1a2a3a4b1b2b3b4 就成了 a1a2b3b2
: a3a4b3b4
: 两个单元, 每个单元再套用这个办法 ,奇数太麻烦了, 我估计就放弃了
X*K
45 楼
前几天看了发现换来换去的没概念，撂在一边。今天一看，不就是个排序的问题吗。把
数字做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 的大作中提到】
: 假设有一个数组：
: 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)更好的算法。
数字做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 的大作中提到】
: 假设有一个数组：
: 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
46 楼
先看看回帖再下结论，不要那么想当然
【在 X*K 的大作中提到】
: 前几天看了发现换来换去的没概念，撂在一边。今天一看，不就是个排序的问题吗。把
: 数字做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
47 楼
恩。。用某种数学方法是可以O(n)的
我问过acm牛人。。
【在 q****x 的大作中提到】
: 置换群？
我问过acm牛人。。
【在 q****x 的大作中提到】
: 置换群？
X*K
48 楼
怎么是想当然呢，你给个in-place O(n)的算法，那么同样那可以用来
把两个排好序的数组in-place归并，那恭喜你，你找到了in-place的
merge sort算法，牛大了。
【在 h*******e 的大作中提到】
:
: 先看看回帖再下结论，不要那么想当然
把两个排好序的数组in-place归并，那恭喜你，你找到了in-place的
merge sort算法，牛大了。
【在 h*******e 的大作中提到】
:
: 先看看回帖再下结论，不要那么想当然
X*K
49 楼
OK不对，这题应该是归并两个排好序数组的特例，希望能看到O(N)的方法。
【在 X*K 的大作中提到】
: 怎么是想当然呢，你给个in-place O(n)的算法，那么同样那可以用来
: 把两个排好序的数组in-place归并，那恭喜你，你找到了in-place的
: merge sort算法，牛大了。
【在 X*K 的大作中提到】
: 怎么是想当然呢，你给个in-place O(n)的算法，那么同样那可以用来
: 把两个排好序的数组in-place归并，那恭喜你，你找到了in-place的
: merge sort算法，牛大了。
H*r
50 楼
这篇paper:
http://arxiv.org/pdf/0805.1598v1.pdf
【在 S*******e 的大作中提到】
: 假设有一个数组：
: 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)更好的算法。
http://arxiv.org/pdf/0805.1598v1.pdf
【在 S*******e 的大作中提到】
: 假设有一个数组：
: 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
51 楼
应该是用置换群的理论
这个mod的函数其实就是一个2n->2n的置换么
把这个permutation拆成cycles以后
把每个cycle都做一遍变换
就是把这个cycle里面的元素都放到了合适的位置
所有cycle都走遍的时候就完成了shuffle
时间上就是O(n)了
【在 d**********x 的大作中提到】
: 恩。。用某种数学方法是可以O(n)的
: 我问过acm牛人。。
这个mod的函数其实就是一个2n->2n的置换么
把这个permutation拆成cycles以后
把每个cycle都做一遍变换
就是把这个cycle里面的元素都放到了合适的位置
所有cycle都走遍的时候就完成了shuffle
时间上就是O(n)了
【在 d**********x 的大作中提到】
: 恩。。用某种数学方法是可以O(n)的
: 我问过acm牛人。。
g*x
52 楼
Agree. How to get those cycles in O(1) space?
【在 C***U 的大作中提到】
: 应该是用置换群的理论
: 这个mod的函数其实就是一个2n->2n的置换么
: 把这个permutation拆成cycles以后
: 把每个cycle都做一遍变换
: 就是把这个cycle里面的元素都放到了合适的位置
: 所有cycle都走遍的时候就完成了shuffle
: 时间上就是O(n)了
【在 C***U 的大作中提到】
: 应该是用置换群的理论
: 这个mod的函数其实就是一个2n->2n的置换么
: 把这个permutation拆成cycles以后
: 把每个cycle都做一遍变换
: 就是把这个cycle里面的元素都放到了合适的位置
: 所有cycle都走遍的时候就完成了shuffle
: 时间上就是O(n)了
g*x
53 楼
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 的大作中提到】
: Agree. How to get those cycles in O(1) space?
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 的大作中提到】
: Agree. How to get those cycles in O(1) space?
相关阅读
统计买买提商机无限啊！！！！内蒙古一限拆通知附子弹车通人性 （长，慎入） (转载)女BP晒黑了娶谁也不能娶中国人zz[女AP练瑜伽]瑜伽姐PK ?你们AP, RA的搞了一个多月Re: 好像解释是这样的 (转载)打方肘子的工程确实经过了转包Re: 太祖当年邀请少奇夫人单独游泳这事太菲夷所思了！！！ (转(转载)昨天吃了祖国送来的月饼 (转载)玩AP裸照的就不能在标题注明一下？发现DFBB词条居然上了urban dictionary中秋之夜讲人权六种睡姿六种性格Re: NND,在美国头一回碰见这种恶人. (转载)外F女榜样：左手毕业证 右手结婚证 留英一年成都女孩回乡创业 ( (转载)狗狗RARe: 这到底是怎么回事？ (转载)