一道google的面试题（转自瀚海星云）

imlmm
等级:

发表于：2007-12-29 23:10:167楼得分:0

/************************************************************************************************
输入a_1, a_2, ..., a_n, b_1, b_2, ..., b_n，如何在O(n)的时间，用O(1)的空间，
将这个序列顺序改为a_1, b_1, ..., a_n, b_n。
1> a_1, b_1, a_3, a_4, a_5, a_6, a_2, b_2, b_3, b_4, b_5, b_6
2> a_1, b_1, a_2, a_4, a_5, a_6, a_3, b_2, b_3, b_4, b_5, b_6
************************************************************************************************/
#include <iostream>

using namespace std;

void order(int* p, int size)
{
if( size % 2 != 0 ¦ ¦ size <= 2) // 两项以内不需要移动
return;

// 首先把第二个数取出来, 这样第2项就空出来了, 然后计算应该哪一项要移到第二个位置;
// 这样移动后又空出一项..., 一直计算到正好要填上得就是第二项, 结束移动
int temp = p[1];
int index = -1; // 用于保存要移到空位置得项得索引
index = size / 2;
p[1] = p[index];

while(index != 1)
{
if(index % 2 == 0) // 需要把a中某一项移入
{
p[index] = p[index / 2];
index = index / 2;
}
else
{
p[index] = p[index / 2 + size / 2];
index = index / 2 + size / 2;
}
}
if(index == 1)
p[index] = temp;
else
cout < < "error";
}

void testOrder()
{

int pp[] = {101, 102, 103, 104, 105, 106, 107, 201, 202, 203, 204, 205, 206, 207};
order(pp, 14);

for(int i = 0; i < 4; i++)
cout < < pp[i] < < " ";
}

void main()
{
testOrder();
getchar();
}

修改删除举报引用回复

void test() { for(int j=1; j<100;j++) { int N = j; int* a = new int[2*N]; for(int i=0; i<N; i++) { a[i]=i+1; a[N+i]=-(i+1); } order(a,2*N); if(!check(a,2*N)) { cout<<N<<" "; } delete[] a ; } }

#include "Stdio.h" #include "Conio.h" int main(void) { int n[]={1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90}; int i,j=2,temp,num=9,max=0; for(i=1;i<num;i+=2){ /*先空跑一遍*/ while((i*j)%(2*num-1)!=i){ max++; j*=2; } j=2; if (max>2*num-3) break; } pp: max=i; /*MAX-2是最大位，由于下面那个循环用了i<max，所以不用max=i就行了*/ for(i=1;i<max;i+=2){ while((i*j)%(2*num-1)!=i){ temp=n[i]; n[i]=n[(i*j)%(2*num-1)]; n[(i*j)%(2*num-1)]=temp; j*=2; } j=2; } for(i=0;i<2*num;i++) printf("%d ",n[i]); getch(); return 0; }

void main() { int arr[2*N+1]={0,1,2,3,4,5,6,7,8,9,10}; ReOrder(arr,5); } void ReOrder(int *arr,int n) { if(n == 1) { return ;//do nothing; } for(int m=2;m<n;m++) { int temp = arr[2]; for(int k =2;k<2*m-2;k+=2) { arr[k] = arr[k+2]; } arr[2*m-2] = arr[2*m-1]; arr[2*m-1] = temp; } }

void ReOrder(int *arr,int n) { //第0单元无效，用作临时变量 if(n == 1) { return ;//do nothing; } for(int m=2;m<=n;m++) { arr[0] = arr[2]; for(int k =2;k<2*m-2;k+=2) { arr[k] = arr[k+2]; } arr[2*m-2] = arr[2*m-1]; arr[2*m-1] = arr[0]; } } void main() { const int N =6; int arr[2*N+1]={0,1,3,5,7,9,11,2,4,6,8,10,12}; //{0,1,2,3,4,5,6,7,8,9,10}; ReOrder(arr,N); }

#include <stdio.h> #define N 10 int num[N * 2]; void disp() { int i; for(i = 0; i < 2 * N; i++) { printf("%03d ", num[i]); } printf("\n"); } void arrange() { unsigned i, n = N * 2 - 1; int t; i = n - 2; t = num[i]; num[i] = num[i + 1]; while(i != n - 1) { if