一个朋友的面试题(有兴趣者请进) ( 积分: 0 )

  • 主题发起人 主题发起人 yihanyan
  • 开始时间 开始时间
忙了半天,问题还是出在顺序上——不用递归和数组的话,时间复杂度始终是问题。
下面的代码通过一遍扫描将奇数和偶数分区(统计信息已经在上一步完成),通过简单的
“标记”方法,将每个分区中的数字都分为两种——一种是位置没有动过的“原住民”,另
一种是从另一个分区中交换过来的“拆迁户”,并且,后者的次序是反序排列的。
//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) :(
不过,也许我们能够通过对数组元素的加减运算找到新的窍门也说不定 :P
题目只是要求不能“定义”数组用于数据交换,并没有说要限制空间复杂度(个人认为算
法的指令空间以及执行时所需的运行空间都应该要考虑进去的),jeffrey_s兄的算法干净
利落,佩服啊 :)
 
呵呵,不再分数多少,主要是问题有意思。
jeffrey_s的实现方式目前来说,应该是最合理的了
 
如果动用一个以上的辅助存储位置,如栈空间 或数组
可以做到时间复杂度为 O(n)
如果只允许使用一个辅助存储空间,就用直接插入法进行排序,时间复杂度为 O(n*n)
 
不错的帖子
 
为何偶的不行?代码简单且循环绝没超过N次呀,哪位测试过的说说!
 
你的是双重循环,时间复杂度是 O(N*N)
 
这次绝对只使用了一次N值,只使用了一个while主循环,中间的数据移动使用的while应该不算吧(就是算进去,也不是N*N),各位看看合不合题意
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Memo1: TMemo;
Edit1: TEdit;
procedure Button1Click(Sender: TObject);
procedure PrintIntArray(pi: PInteger;
ACount: Integer);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;
implementation
{$R *.dfm}
procedure TForm1.PrintIntArray(pi: PInteger;
ACount: Integer);
var
i: Integer;
begin
Memo1.Lines.begin
Update;
try
for i := 0 to ACount - 1do
begin
Memo1.Lines.Add(IntToStr(pi^));
Inc(pi);
end;

Memo1.Lines.Add('*******************************')
finally
Memo1.Lines.EndUpdate;
end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
i: Integer;
iCount: Integer;
a: array of Integer;
tempinteger:integer;
j:integer;
jj:integer;
begin
Memo1.Clear;
try
iCount := StrToInt(Edit1.Text);
//可以用Edit中输入指定元素个的数组
except
iCount := 100;
end;
//初始化数组
SetLength(a, iCount);
Randomize;
for i := 0 to iCount - 1do
a := Random(iCount * 2) + 1;
//还是用随机数做测试
//a := i + 1;
//输出原始数组
PrintIntArray(@a[0], iCount);
//新的算法从此开始,只有一个循环,中间的数据移动不应算次数吧?
i:=0;
j:=0;
while i<icountdo
begin
if (a mod 2)=0 then
//是偶数
begin
if j=0 then
tempinteger:=a;
//保存待交换的数据,但暂不交换,仅做偏移记录
j:=j+1;

end else
//当遇到奇数
begin
//偏移变量>0时才交换
if j>0 then

begin
if j=1 then
//仅隔一位是偶数的情况,就直接做交换
begin
a[i-j]:=a;
//先前位数据=当前位数据
a:=tempinteger;
//当前位=先前位
end else
begin
//连续偶数的情况,先将偶数数据全部后移,然后再交换
tempinteger:=a;
//先保存当前位奇数值
jj:=0;

while jj<=jdo
//将偶数数据后移
begin

a[i-jj]:=a[i-jj-1];//a:=a[i-1]
jj:=jj+1;
end;
a[i-j]:=tempinteger;
//先前位数据=当前位数据
end;
i:=i-j+1;
//原位置交换位的下一位
j:=0;
//交换后将偏移置为0
continue;

end;
end;
i:=i+1;
end;
//----------------算法结束--------------------------
//输出排序后的数组,查看结果是否正确
PrintIntArray(@a[0], iCount);
end;

end.
 
那你说直接插入法排序的时间复杂度是多少呢?
数据移动也是要有开销的
 
偶也不知道该如何算,因为本算法是因奇偶数的不同而运行的次数不同的.但可以将随机数组理想话(大量的随机数组测试的话,应该趋于奇偶均匀分布),所以我们可以用数组1..100来作测试来计算算法的的运行次数.
如果我们的数组是1..100的话,N*N=10000,偶在程序中加入一个计数器X来计算回退指针的次数,得到的结果是1325次指针移动(0..N的主循环+x回退指针操作的次数),程序如下:
procedure TForm1.Button1Click(Sender: TObject);
var
i: Integer;
iCount: Integer;
a: array of Integer;
tempinteger:integer;
j:integer;
jj:integer;
x:integer;
//回退操作计数器
begin
Memo1.Clear;
try
iCount := StrToInt(Edit1.Text);

except
iCount := 100;
end;
//初始化数组
SetLength(a, iCount);
Randomize;
for i := 0 to iCount - 1do
//a := Random(iCount * 2) + 1;
//不用随机数做测试
a := i + 1;
//使用1..100数据,平均分布奇偶数
//输出原始数组
PrintIntArray(@a[0], iCount);
//新的算法从此开始
i:=0;
j:=0;
x:=0;
while i<icountdo
begin
if (a mod 2)=0 then
//是偶数
begin
if j=0 then
tempinteger:=a;
//保存待交换的数据,但暂不交换,仅做偏移记录
j:=j+1;

end else
//当遇到奇数
begin
//偏移变量>0时才交换
if j>0 then

begin
if j=1 then
//仅隔一位是偶数的情况,就直接做交换
begin
a[i-j]:=a;
//先前位数据=当前位数据
a:=tempinteger;
//当前位=先前位
x:=x+1;
//指针回退1位,计数器+1;
end else
begin
//连续偶数的情况,先将偶数数据全部后移,然后再交换
tempinteger:=a;
//先保存当前位奇数值
jj:=0;
while jj<=jdo
//将偶数数据后移
begin

a[i-jj]:=a[i-jj-1];//a:=a[i-1]
jj:=jj+1;
end;
a[i-j]:=tempinteger;
//先前位数据=当前位数据
x:=x+j;
//指针回退j位,这里计数
end;
i:=i-j+1;
//原位置交换位的下一位
j:=0;
//交换后将偏移置为0
continue;

end;
end;
i:=i+1;
end;
//----------------算法结束--------------------------
//输出排序后的数组,查看结果是否正确
PrintIntArray(@a[0], iCount);
showmessage(inttostr(icount+X));
//结果是1325次
end;

end.
 
再次想了想,觉得不能将数据移动的部份计入在内.否则,即便允许使用辅助空间,次数也绝对大于N(在有辅助空间时,先是检出偶数,已经遍列了一次,然后排序到另一空间,又是一次,最后覆盖回原数组,又是一次,这样岂不是N+N+N了,那么就永远无法满足题意了.当然,也不一定就是这样操作,也可以用二维数组来捡出来时同时记住原数组下标,然后直接覆盖回原数组的相应下标单元中,这样也是N+N,但这样也是N+N呀!)
push pop movsb sort 等操作也是要花时间的.要绝对的0(N)那就办不到了
 
用最苯的方法用一无限循环
每次循环都把奇数向前一位.并记录下有多少次向前移动奇数的次数.
直到到一次都没有的时候就退出来.这样奇数就跑到前面去了.
 
对于时间复杂度来说,3*N, 1000*N 都认为是 O(N)
说的是所用时间和 任务个数的关系,
O(N) 表示和 N成线性关系
O(N×N)表示和 N*N 成线性关系
这里区别就大了,尤其是随着元素个数的增加,
 
jeffrey_s 的算法我测了,数组长度 50000 以内的时间复杂度0(n),再长就溢出了,没测
个人认为这是最好的办法了
 
DLL.gif
 
如果是排了還要按照順序的話,就沒有答案了,O(N)是什么概念噢。。。如果是從後面開始的話兩兩交換就可以實現了,但有序就不可能了
 
后退
顶部