问个关于汉声数学图画书的问题# Parenting - 为人父母
d*x
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;
}
,这点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
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
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;
}