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 的大作中提到】
: 遇到这题直接跪了
|
S*******e
发帖数: 379 | 4 什么意思？直接放弃？
【在 w****x 的大作中提到】
: 遇到这题直接跪了
|
h**********l
发帖数: 6342 | 5 没有吧
这个之前讨论的正数负数分开那个是一样的
【在 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)更好的算法。
|
v****c
发帖数: 29 | 6 不知道有没有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)更好的算法。
|
w****x
发帖数: 2483 | 7
以前版上讨论过, 后来自己想了两小时无果
【在 p*****2 的大作中提到】
:
: 同跪。等高人。记得讨论过无解是吗？
|
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 的大作中提到】
: 对于每一个数字，我们是知道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 的大作中提到】
:
: "对于每一个数字，我们是知道shuffle之后的位置的"
: 谁说的, 要是是这样的:12nfwdfo9r83r92bejrr8172r @$!#
: 你咋看的出来??
|
|
|
t**********h
发帖数: 2273 | 11 如果是这样的话，
那么每个ai和bi有一个初始位置，我们知道，题目已给。ai和bi还有一个结束位置，我
们知道，题目已给，那么是可以建立一个初始到结束的映射函数来弄的。
比如从b1开始，它是要占a2的位置的，那么把a2拎起来，存在tmp，然后b1占a2的位置
，然后tmp（这时为a2）找自己的终结位置，找到后，把他拎起来，占位，然后继续下
去。。。。
【在 t**********h 的大作中提到】
: 我觉得他的意思是说前半截a1到an排好序了，后半截b1到bn排好序了，这样来扔。看原
: 题的描述，似乎是从b1这个数字的下标开始，每个bi依次往ai插
: 如果是这样的，和我们之前讨论的那个奇数往前扔，偶数往后扔，但是要保持原来的顺
: 序那道题是不一样
|
v****c
发帖数: 29 | 12 问题是这么一轮下去后，你怎么知道哪些已经被放好了，哪些没有放好呢？
就是说下一轮你怎么处理b2？他有可能需要处理有可能不需要处理了
【在 t**********h 的大作中提到】
: 如果是这样的话，
: 那么每个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 的大作中提到】
: 假设有一个数组：
: 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 的大作中提到】
: nlogn怎么解?? 怎么分治, 想不出来, 请教一下
|
w****x
发帖数: 2483 | 16
哦,想出来了
a1a2a3a4b1b2b3b4 ==> a1a2b2b1a4a3b3b4 ==> a1a2b1b2 a3a4b3b4
【在 r*****e 的大作中提到】
: cup150里面有这道题啊，就是D&C的思想，虽然那个答案看起来
: 有点不太对劲。我是觉得奇偶的情况好像没有考虑，code自己没写，
: 觉得太麻烦。做好投降的准备了，呵呵。
|
w****x
发帖数: 2483 | 17 严格来说这样的不算divided & conquer吧, 算conquer then divide |
c****p
发帖数: 6474 | 18 有啊，perfect shuffle
【在 p*****2 的大作中提到】
:
: 同跪。等高人。记得讨论过无解是吗？
|
c****p
发帖数: 6474 | 19 和正负数分开不太一样
【在 h**********l 的大作中提到】
: 没有吧
: 这个之前讨论的正数负数分开那个是一样的
|
r*****e
发帖数: 792 | 20 中间那步应该是a1a2b1b2a3a4b3b4吧？
也许你这么做也成。
【在 w****x 的大作中提到】
: 严格来说这样的不算divided & conquer吧, 算conquer then divide
|
|
|
w****x
发帖数: 2483 | 21
你说的就是我的第3步啊, 两次反转嘛
【在 r*****e 的大作中提到】
: 中间那步应该是a1a2b1b2a3a4b3b4吧？
: 也许你这么做也成。
|
S*******e
发帖数: 379 | 22 展开讲讲？
是说分成4份，交换第二和第三个quarter吗？
如果总长是个奇数呢？
【在 w****x 的大作中提到】
:
: 你说的就是我的第3步啊, 两次反转嘛
|
w****x
发帖数: 2483 | 23
每个单元反转中段, 再反转中段的两个半段 a1a2a3a4b1b2b3b4 就成了 a1a2b3b2
a3a4b3b4
两个单元, 每个单元再套用这个办法 ,奇数太麻烦了, 我估计就放弃了
【在 S*******e 的大作中提到】
: 展开讲讲？
: 是说分成4份，交换第二和第三个quarter吗？
: 如果总长是个奇数呢？
|
q****x
发帖数: 7404 | 24 置换群？
【在 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
发帖数: 792 | 25 我也是觉得奇数时太麻烦所以没写成code，就打算口述思想了，呵呵。
【在 w****x 的大作中提到】
:
: 每个单元反转中段, 再反转中段的两个半段 a1a2a3a4b1b2b3b4 就成了 a1a2b3b2
: a3a4b3b4
: 两个单元, 每个单元再套用这个办法 ,奇数太麻烦了, 我估计就放弃了
|
p*****o
发帖数: 1285 | 26 这个方法类似于那个给一个序列找第一个缺少的正数一样。但有一个假定是可以根据数
字本身确定它的最终位置， 对这个题似乎不成立。
【在 z******t 的大作中提到】
: 对于每一个数字，我们是知道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 的大作中提到】
: 假设有一个数组：
: 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 的大作中提到】
: 下面这个是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 的大作中提到】
: 偷一位当存储不能算原地.
|
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 的大作中提到】
: 没有违反下面说法啊？ 怎么定义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 的大作中提到】
: 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 的大作中提到】
:
: 每个单元反转中段, 再反转中段的两个半段 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 的大作中提到】
: 假设有一个数组：
: 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 的大作中提到】
: 前几天看了发现换来换去的没概念，撂在一边。今天一看，不就是个排序的问题吗。把
: 数字做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 的大作中提到】
: 置换群？
|
X*K
发帖数: 87 | 38 怎么是想当然呢，你给个in-place O(n)的算法，那么同样那可以用来
把两个排好序的数组in-place归并，那恭喜你，你找到了in-place的
merge sort算法，牛大了。
【在 h*******e 的大作中提到】
:
: 先看看回帖再下结论，不要那么想当然
|
X*K
发帖数: 87 | 39 OK不对，这题应该是归并两个排好序数组的特例，希望能看到O(N)的方法。
【在 X*K 的大作中提到】
: 怎么是想当然呢，你给个in-place O(n)的算法，那么同样那可以用来
: 把两个排好序的数组in-place归并，那恭喜你，你找到了in-place的
: merge sort算法，牛大了。
|
H****r
发帖数: 2801 | 40 这篇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)更好的算法。
|
|
|
C***U
发帖数: 2406 | 41 应该是用置换群的理论
这个mod的函数其实就是一个2n->2n的置换么
把这个permutation拆成cycles以后
把每个cycle都做一遍变换
就是把这个cycle里面的元素都放到了合适的位置
所有cycle都走遍的时候就完成了shuffle
时间上就是O(n)了
【在 d**********x 的大作中提到】
: 恩。。用某种数学方法是可以O(n)的
: 我问过acm牛人。。
|
g**x
发帖数: 373 | 42 Agree. How to get those cycles in O(1) space?
【在 C***U 的大作中提到】
: 应该是用置换群的理论
: 这个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 的大作中提到】
: Agree. How to get those cycles in O(1) space?
|
