C
creation-zy
Unregistered / Unconfirmed
GUEST, unregistred user!
忙了半天,问题还是出在顺序上——不用递归和数组的话,时间复杂度始终是问题。
下面的代码通过一遍扫描将奇数和偶数分区(统计信息已经在上一步完成),通过简单的
“标记”方法,将每个分区中的数字都分为两种——一种是位置没有动过的“原住民”,另
一种是从另一个分区中交换过来的“拆迁户”,并且,后者的次序是反序排列的。
//Step2: 带标记的奇偶交换 O(N*1)
P_Div:=Low(IntAy)+JCount-1;
//奇偶分界点
P1:=P_Div;
P2:=High(IntAy);
while P2>P_Divdo
//在此,以偶指针P2为主动指针,奇指针P1为从动指针
begin
if IntAy[P2] and $1=0 then
Dec(P2) //偶指针遇到偶数 -> 向头部前进
else
begin
//偶指针遇到了奇数,需要进行奇偶交换
while IntAy[P1] and $1=1do
//奇指针遇到奇数 -- 同上
Dec(P1);
//数据交换——目标:将所有的奇数放都在偶数的左边
//在交换的同时对双方都执行加1的操作,以改变奇偶性,打上“交换标记”,以便后面的次序恢复
// -- 在此采用了两个中间变量,便于阅读 --
TmpInt1:=IntAy[P1]+1;
TmpInt2:=IntAy[P2]+1;
IntAy[P2]:=TmpInt1;
//+1后的偶数
IntAy[P1]:=TmpInt2;
//+1后的奇数
//交换完毕,奇偶指针都要继续前进
Dec(P2);
Dec(P1);
end;
end;
即便完成了奇偶交换,现在又形成了新的问题——将原有的以及被交换过来的数字进行重
组——还是没逃掉。我又写了一个原理简单的纯重组算法(相邻奇偶区块顺序互换),可惜
通过试验,复杂度为O(n*n)
不过,也许我们能够通过对数组元素的加减运算找到新的窍门也说不定
题目只是要求不能“定义”数组用于数据交换,并没有说要限制空间复杂度(个人认为算
法的指令空间以及执行时所需的运行空间都应该要考虑进去的),jeffrey_s兄的算法干净
利落,佩服啊
下面的代码通过一遍扫描将奇数和偶数分区(统计信息已经在上一步完成),通过简单的
“标记”方法,将每个分区中的数字都分为两种——一种是位置没有动过的“原住民”,另
一种是从另一个分区中交换过来的“拆迁户”,并且,后者的次序是反序排列的。
//Step2: 带标记的奇偶交换 O(N*1)
P_Div:=Low(IntAy)+JCount-1;
//奇偶分界点
P1:=P_Div;
P2:=High(IntAy);
while P2>P_Divdo
//在此,以偶指针P2为主动指针,奇指针P1为从动指针
begin
if IntAy[P2] and $1=0 then
Dec(P2) //偶指针遇到偶数 -> 向头部前进
else
begin
//偶指针遇到了奇数,需要进行奇偶交换
while IntAy[P1] and $1=1do
//奇指针遇到奇数 -- 同上
Dec(P1);
//数据交换——目标:将所有的奇数放都在偶数的左边
//在交换的同时对双方都执行加1的操作,以改变奇偶性,打上“交换标记”,以便后面的次序恢复
// -- 在此采用了两个中间变量,便于阅读 --
TmpInt1:=IntAy[P1]+1;
TmpInt2:=IntAy[P2]+1;
IntAy[P2]:=TmpInt1;
//+1后的偶数
IntAy[P1]:=TmpInt2;
//+1后的奇数
//交换完毕,奇偶指针都要继续前进
Dec(P2);
Dec(P1);
end;
end;
即便完成了奇偶交换,现在又形成了新的问题——将原有的以及被交换过来的数字进行重
组——还是没逃掉。我又写了一个原理简单的纯重组算法(相邻奇偶区块顺序互换),可惜
通过试验,复杂度为O(n*n)
不过,也许我们能够通过对数组元素的加减运算找到新的窍门也说不定
题目只是要求不能“定义”数组用于数据交换,并没有说要限制空间复杂度(个人认为算
法的指令空间以及执行时所需的运行空间都应该要考虑进去的),jeffrey_s兄的算法干净
利落,佩服啊