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

小

小红河

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-12

• #41

不难.........

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-13

• #42

楼主最好明确一下题意，题目的输入肯定是1,2,3,4,……99,100这样子的吗？
还是说肯定是这100个数，只是顺序随机，还是数的个数的顺序都是完全随机的？

 

D

djh_djh

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-13

• #43

算法复杂度度是 o就可以了
分别从两头扫描
n = 99;
m = 0;
while (n > m)
{
while (a[n] 是 偶数)
{
n --;
}
if (n > 0)//找到了后面的奇数
{
while (m < n 且 a[m] 是奇数)
{
m++
}
if (m < n )
{
交换a[m] a[n]
}
}
}

 

W

wangsea

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-13

• #44

估计偶的这个最简单啦
//输出照抬前面兄弟的
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;
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[0..99]
//a := i + 1;
//输出原始数组
PrintIntArray(@a[0], iCount);

//这个部份是偶的算法-------------------------
i:=0;
while i<iCountdo
begin
if (a mod 2)=0 then
//若当前是偶数
begin
for j:=i+1 to iCount-1do
if (a[j] mod 2)=1 then
//在其后找到第一个奇数
begin
tempinteger:=a;
a:=a[j];
a[j]:=tempinteger;
break;
//找到第一个即终止For循环
end;
end;
i:=i+1;
end;
//现在a[0..x]都是奇数,a[x+1..99]都是偶数,且原来先后顺序不变----------------
//输出排序后的数组
PrintIntArray(@a[0], iCount);
end;

 

Y

yihanyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-14

• #45

to:AI_Player
数组的数据是不确定的，任意的，什么都行
我说的1 3 5..97 99 2 4 6 ..98 100指的是原数组的下标

 

放

放飞

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-14

• #46

我最后一次给你的程序就能满足你的要求：
数组内容任意
排序后，奇数在前，偶数在后，并保持原来奇数、偶数的先后位置不变
时间复杂度为o
(我提供的算法在完成最后一次奇数、偶数交换后就会退出，不一定非要循环100次,换句话说，最理想的情况下：有多少个奇数就会循环多少次)

 

M

monkeyking1983

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-14

• #47

我觉得你们把题目想复杂了，只要直接给书组付值就好了，何必要倒来倒去。
这样很快就能保证时间复杂度是O。
题目里面没有写不允许使用付值的方法

 

U

utop

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-14

• #48

procedure TForm1.Button1Click(Sender: TObject);
var
n : array[1..100] of integer;
i, iLast, iTemp : Integer;
begin
for i := 1 to 100do
n := i;
iLast := 0;
for i := 1 to 100do
begin
if n mod 2 <> 0 then
begin
iTemp := n;
CopyMemory(@n[iLast + 2], @n[iLast + 1], (i - iLast - 1) * 4);
inc(iLast);
n[iLast] := iTemp;
end;
end;

memo1.Clear;
for i := 1 to 100do
memo1.Lines.Append(IntToStr(n));
end;

改了改

 

绵

绵绵细雨

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-14

• #49

procedure TForm1.Button1Click(Sender: TObject);
var aa:array[1..100] of integer;
i,j,j1:integer;
begin
ListBox1.Items.Clear;
ListBox2.Items.Clear;
for i:=1 to 100do
begin
aa := trunc(Random(1000));
ListBox1.Items.Append(IntToStr(aa));
end;
j1:=101;
i:=1;
//for i:=1 to 100do
while i<j1do
begin
//if i>=j then
break;
if aa mod 2=0 then
begin
for j:=j1-1do
wnto i+1do
begin
if aa[j] mod 2=1 then
begin
aa := aa+aa[j];
aa[j] := aa-aa[j];
aa := aa-aa[j];
j1 := j;
break;
end;
end;
end;
inc(i);
end;

for i:=1 to 100do
begin
ListBox2.Items.Append(IntToStr(aa));
end;
end;

 

L

likekoko

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-14

• #50

同意 差不多算了！呵呵。

 

H

hwh6666

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-14

• #51

为什么这一句会出错呢?
mmo1.Lines.Add(IntToStr(a));

 

Y

yihanyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-14

• #52

to:放飞
你好厉害哦！

 

D

djh_djh

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-14

• #53

其实这个简单的算法 就是数据结构 中的 快速排序, 中的一次排序,
换了一个名字而己, 应该想都不用想的

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-15

• #54

to 放飞：
因为没装delphi，没法单步调试，所以只是粗略的看了一下你的算法，感觉时间不是O的。首先你在Button1Click中已经有了一重循环，时间已经是O了，然后每次循环你还用了递归。递归的时间似乎也是O，起码不是O(1)的。所以你总的时间是肯定高于O的。时间复杂度一般看的是最差情况，而不是最好情况。

 

U

utop

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-15

• #55

呵呵，正因为要求O，我认为不用CopyMemory是不可能的
补充:我是想说,如果不用CopyMemory的方法,采用循环或者递归捣来捣去的算法是不能达到O的要求的

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-15

• #56

CopyMemory只能提高运行速度，但并不会降低时间复杂度

 

龙

龙丹

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-15

• #57

所有科班出身的肯定都学过交换排序(快速排序)，就不知道活学活用？
type
TDataArr=array[1..100] of Integer;
procedure SortX(var A:TDataArr);
var
i,j,x:Integer;
begin
i:=1;
j:=100;
while i<jdo
begin
if not Odd(A) then
begin
if Odd(A[j]) then
//Swap(i,j)
begin
x:=A[j];
A[j]:=A;
A:=x;
Inc(i);
end;
Dec(j);
end
else
Inc(i);
end;
end;

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-15

• #58

再次说明一遍吧，顶楼的帖子没有说完整，不仅仅要求奇数在前偶数在后，还有求奇数与奇数之间、偶数与偶数之间的相对顺序不变。简单的用类似快排的交换会打乱奇数或者偶数的顺序，所以是行不通的。拜托大家回帖时先把前面的讨论看完。

 

S

SS2000

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-15

• #59

既要时间复杂度为O,又不能加辅助数组空间，并且顺序相对不变---难（我目前没想出算法）

 

H

hcm0790

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-15

• #60

简而言之就是将A,B而变量互换, 但不定义第三个变量, 故较简单.
A := A+B ;
B := A-B ;
A := A-B ;