d**********x
发帖数: 4083 | 1 实际上是O(logn)的空间，但是既然长度为2^32的数列可以借助一个int来作为辅助空间
，这点overhead基本可以忽略不计了。欢迎找bug：
#include
#include
#include
using namespace std;
#include
static int get_index(int i) {
if (i == 0) {
return 1;
}
return (1 << i) + 1;
}
void rearrange(vector& vec) {
int bitmap = 0; //"O(1)" space for length < (1 << 32)
int k = vec.size() / 2;
int n = vec.size();
for (int i = 0; get_index(i) < k; ++i) {
int cur = get_index(i);
if ((1 << i) & bitmap) {
continue;
}
int next = cur * 2;
string tmp = vec[cur];
while (1) {
if (((next - 1) & (next - 2)) == 0) {
bitmap |= (next == 1 ? 1 : (next - 1));
}
string tmp2 = vec[next];
vec[next] = tmp;
tmp = tmp2;
cur = next;
if (cur == get_index(i)) {
break;
}
if (next >= k) {
next = cur - (n - 1 - cur);
} else {
next = cur * 2;
}
}
}
}
int main() {
for (int i = 1; i <= 100; ++i) {
vector v(i * 2);
char buf[128];
for (int j = 0; j < i; ++j) {
sprintf(buf,"%d",j + 1);
v[j] = string("a") + buf;
v[j + i] = string("b") + buf;
}
for (int j = 0; j < i * 2; ++j) {
cout << v[j] << ' ';
}
cout << endl;
rearrange(v);
for (int j = 0; j < i * 2; ++j) {
cout << v[j] << ' ';
}
cout << endl;
}
return 0;
} |
c********t
发帖数: 5706 | 2 是吧a1a2a3...b1b2b3 排成 a1b1a2b2a3b3...吗？我正在找这个解法呢。
【在 d**********x 的大作中提到】
: 实际上是O(logn)的空间，但是既然长度为2^32的数列可以借助一个int来作为辅助空间
: ，这点overhead基本可以忽略不计了。欢迎找bug：
: #include
: #include
: #include
: using namespace std;
: #include
: static int get_index(int i) {
: if (i == 0) {
: return 1;
|
d**********x
发帖数: 4083 | 3 是。。。
算法是观察交换的规律，发现如果把交换拆成若干个轮换集合的话，总是从
0, 1, 3, 7, ..., 2^n - 1这类下标开始的
但是在交换的过程中，可能有一些集合实际上是交叉在一起的，所以需要一个辅助空间
来表明某个集合是否已经被处理过
空间
【在 c********t 的大作中提到】
: 是吧a1a2a3...b1b2b3 排成 a1b1a2b2a3b3...吗？我正在找这个解法呢。
|
M*********n
发帖数: 4839 | 4 大侠，
老印的网站上给了个真正的的o（1）space， O（n）time的：
http://www.geeksforgeeks.org/an-in-place-algorithm-for-string-t
这个solution很难想，原理是有些长度的序列经过O(n)次操作就可以一次得到结果。
这些长度是，3^K+1.
【在 d**********x 的大作中提到】
: 是。。。
: 算法是观察交换的规律，发现如果把交换拆成若干个轮换集合的话，总是从
: 0, 1, 3, 7, ..., 2^n - 1这类下标开始的
: 但是在交换的过程中，可能有一些集合实际上是交叉在一起的，所以需要一个辅助空间
: 来表明某个集合是否已经被处理过
:
: 空间
|
d**********x
发帖数: 4083 | 5 老印吹牛不上税呗。
先cut 3^k，再cut 3^(k-1)。。。最后相当与cut出来近似log3(n)块(考虑3进制表示)
每次merge他都要reverse一半，3^k直接和n可比，也就是说每次merge都要O(3^k) = O(
n)次操作
最后复杂度是O(nlogn)
空间
【在 M*********n 的大作中提到】
: 大侠，
: 老印的网站上给了个真正的的o（1）space， O（n）time的：
: http://www.geeksforgeeks.org/an-in-place-algorithm-for-string-t
: 这个solution很难想，原理是有些长度的序列经过O(n)次操作就可以一次得到结果。
: 这些长度是，3^K+1.
|
M*********n
发帖数: 4839 | 6 虽然cut成很多块。
但每一块并不是占用O(n)的时间。
O(
【在 d**********x 的大作中提到】
: 老印吹牛不上税呗。
: 先cut 3^k，再cut 3^(k-1)。。。最后相当与cut出来近似log3(n)块(考虑3进制表示)
: 每次merge他都要reverse一半，3^k直接和n可比，也就是说每次merge都要O(3^k) = O(
: n)次操作
: 最后复杂度是O(nlogn)
:
: 空间
|
d**********x
发帖数: 4083 | 7 你再仔细想想。
最坏情况大概有log3n块，这个有问题吗？
第一块长度3^k起码是n/2，有问题吗？
每次reverse需要O(n)，有问题吗？
那个方向是对的，但是老印只知道一知半解抄他引用的那篇paper，抄错了。正确做法
是从短的开始处理，而不是从长的subarray开始。
示)
=
【在 M*********n 的大作中提到】
: 虽然cut成很多块。
: 但每一块并不是占用O(n)的时间。
:
: O(
|
S********t
发帖数: 3431 | 8 看最下面的reference，有paper的
O(
【在 d**********x 的大作中提到】
: 老印吹牛不上税呗。
: 先cut 3^k，再cut 3^(k-1)。。。最后相当与cut出来近似log3(n)块(考虑3进制表示)
: 每次merge他都要reverse一半，3^k直接和n可比，也就是说每次merge都要O(3^k) = O(
: n)次操作
: 最后复杂度是O(nlogn)
:
: 空间
|
d**********x
发帖数: 4083 | 9 看到了，这不妨碍他抄错了。。
示)
=
【在 S********t 的大作中提到】
: 看最下面的reference，有paper的
:
: O(
|
M*********n
发帖数: 4839 | 10
不对， 28第一块是10
不对， 总的reverse加起来是O（n)，每一块只需要reverse一次。
他的code使用递归，实际上就是从短的开始处理。code有点问题，但总体思路是对的。
【在 d**********x 的大作中提到】
: 你再仔细想想。
: 最坏情况大概有log3n块，这个有问题吗？
: 第一块长度3^k起码是n/2，有问题吗？
: 每次reverse需要O(n)，有问题吗？
: 那个方向是对的，但是老印只知道一知半解抄他引用的那篇paper，抄错了。正确做法
: 是从短的开始处理，而不是从长的subarray开始。
:
: 示)
: =
|
|
|
d**********x
发帖数: 4083 | 11
Cut out the largest prefix sub-string of size of the form 3^k + 1. In this
step, we find the largest non-negative integer k such that 3^k+1 is smaller
than or equal to n (length of string)
能看懂最坏情况吗？人家说了，这种情况下直接就是 3^3 +1 = 28。。。再说差个
零头就算了吧，他这个就算不是n/2，也是n/3。因为如果第一次切出来的l比n/3小，则
3*l - 2 仍然是 3^k + 1 的结构而且小于n
是嘛，你能仔细看看他的算法步骤再说话吗？
12345变成54321，然后变成12345678910在变成10987654321，在变成123456789101112
这是reverse了几次？请跟我念：1,2,3,4...
做法
【在 M*********n 的大作中提到】
:
: 不对， 28第一块是10
: 不对， 总的reverse加起来是O（n)，每一块只需要reverse一次。
: 他的code使用递归，实际上就是从短的开始处理。code有点问题，但总体思路是对的。
|
M*********n
发帖数: 4839 | 12 做了个实验，得出如下数据：
左边是数组个数的一半，右边是需要做 cycle leader algorithm的次数，和每次开始
的index：
1->1:{1}
2->1:{1}
3->1:{1}
4->2:{1,3}
5->2:{1,3}
6->1:{1}
7->1:{1}
8->4:{1,3,5,7}
9->2:{1,3}
10->1:{1}
11->5:{1,3,5,7,9}
12->2:{1,5}
13->2:{1,5}
14->3:{1,3,9}
15->1:{1}
16->6:{1,3,5,7,11,15}
17->4:{1,3,5,11}
18->6:{1,3,5,7,15}
19->1:{1}
;;;
其中2，5，14符合规律3^k+1。
很奇怪的是像19,15,10等，可以一次得到结果。但找不出这样的数的规律。 |
c********t
发帖数: 5706 | 13 测一下"ABCDEFGHabcdefgh"，好像是错的啊
【在 d**********x 的大作中提到】
: 实际上是O(logn)的空间，但是既然长度为2^32的数列可以借助一个int来作为辅助空间
: ，这点overhead基本可以忽略不计了。欢迎找bug：
: #include
: #include
: #include
: using namespace std;
: #include
: static int get_index(int i) {
: if (i == 0) {
: return 1;
|
l*******b
发帖数: 2586 | 14 那个尾递归是这样实现的:
a1 a2 a3 a4 a5 a6 a7 b1 b2 b3 b4 b5 b6 b7
swap
a1 a2 a3 a4 b1 b2 b3 b4|a5 a6 a7 b5 b6 b7
shuffle前4个
a1 b1 a2 b2 a3 b3 a4 b4|a5 a6 a7 b5 b6 b7
swap
a1 b1 a2 b2 a3 b3 a4 b4|a5 a6 b5 b6|a7 b7
shuffle
a1 b1 a2 b2 a3 b3 a4 b4|a5 b5 a6 b6|a7 b7
然后好了.对于文章里特定长度的那种序列,是直接实现的,不调用递归 |
d**********x
发帖数: 4083 | 15 nice..看来对8 16 32都错了。。
赶飞机。。回来看
【在 c********t 的大作中提到】
: 测一下"ABCDEFGHabcdefgh"，好像是错的啊
|
c********t
发帖数: 5706 | 16 是不是我改java改的有问题
bitmap判断那句改成下面的是不是对的？
if (((1 << i) & bitmap) != 0) {
continue;
}
static void rearrange(ArrayList list) {
int bitmap = 0; // "O(1)" space for length < (1 << 32)
int k = list.size() / 2;
int n = list.size();
for (int i = 0; get_index(i) < k; ++i) {
int cur = get_index(i);
if (((1 << i) & bitmap) != 0) {
continue;
}
int next = cur * 2;
String tmp = list.get(cur);
while (true) {
if (((next - 1) & (next - 2)) == 0) {
bitmap |= (next == 1 ? 1 : (next - 1));
}
String tmp2 = list.get(next);
list.set(next, tmp);
tmp = tmp2;
cur = next;
if (cur == get_index(i)) {
break;
}
if (next >= k) {
next = cur - (n - 1 - cur);
} else {
next = cur * 2;
}
}
}
}
【在 d**********x 的大作中提到】
: nice..看来对8 16 32都错了。。
: 赶飞机。。回来看
|
d**********x
发帖数: 4083 | 17 没错。。我的算法应该是有问题。。。
看那篇paper吧，我先去机场。。
【在 c********t 的大作中提到】
: 是不是我改java改的有问题
: bitmap判断那句改成下面的是不是对的？
: if (((1 << i) & bitmap) != 0) {
: continue;
: }
: static void rearrange(ArrayList list) {
: int bitmap = 0; // "O(1)" space for length < (1 << 32)
: int k = list.size() / 2;
: int n = list.size();
: for (int i = 0; get_index(i) < k; ++i) {
|
c********t
发帖数: 5706 | 18 ok, have a safe trip!
【在 d**********x 的大作中提到】
: 没错。。我的算法应该是有问题。。。
: 看那篇paper吧，我先去机场。。
|
M*********n
发帖数: 4839 | 19 大侠有工作还面试啊。
【在 c********t 的大作中提到】
: ok, have a safe trip!
|
c********t
发帖数: 5706 | 20 你咋知道我有工作的啊？
【在 M*********n 的大作中提到】
: 大侠有工作还面试啊。
|
