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

  • 主题发起人 主题发起人 yihanyan
  • 开始时间 开始时间
不难.........
 
楼主最好明确一下题意，题目的输入肯定是1,2,3,4,……99,100这样子的吗？
还是说肯定是这100个数，只是顺序随机，还是数的个数的顺序都是完全随机的？
 
算法复杂度度是 o(n)就可以了
分别从两头扫描
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]
}
}
}
 
估计偶的这个最简单啦
//输出照抬前面兄弟的
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;
 
to:AI_Player
数组的数据是不确定的，任意的，什么都行
我说的1 3 5..97 99 2 4 6 ..98 100指的是原数组的下标
 
我最后一次给你的程序就能满足你的要求：
数组内容任意
排序后，奇数在前，偶数在后，并保持原来奇数、偶数的先后位置不变
时间复杂度为o(n)
(我提供的算法在完成最后一次奇数、偶数交换后就会退出，不一定非要循环100次,换句话说，最理想的情况下：有多少个奇数就会循环多少次)
 
我觉得你们把题目想复杂了，只要直接给书组付值就好了，何必要倒来倒去。
这样很快就能保证时间复杂度是O(n)。
题目里面没有写不允许使用付值的方法
 
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;

改了改
 
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;
 
同意 差不多算了！呵呵。
 
为什么这一句会出错呢?
mmo1.Lines.Add(IntToStr(a));
 
to:放飞
你好厉害哦！
 
其实这个简单的算法 就是数据结构 中的 快速排序, 中的一次排序,
换了一个名字而己, 应该想都不用想的
 
to 放飞：
因为没装delphi，没法单步调试，所以只是粗略的看了一下你的算法，感觉时间不是O(n)的。首先你在Button1Click中已经有了一重循环，时间已经是O(n)了，然后每次循环你还用了递归。递归的时间似乎也是O(n)，起码不是O(1)的。所以你总的时间是肯定高于O(n)的。时间复杂度一般看的是最差情况，而不是最好情况。
 
呵呵，正因为要求O(n)，我认为不用CopyMemory是不可能的
补充:我是想说,如果不用CopyMemory的方法,采用循环或者递归捣来捣去的算法是不能达到O(n)的要求的
 
CopyMemory只能提高运行速度，但并不会降低时间复杂度
 
所有科班出身的肯定都学过交换排序(快速排序)，就不知道活学活用？
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;
 
再次说明一遍吧，顶楼的帖子没有说完整，不仅仅要求奇数在前偶数在后，还有求奇数与奇数之间、偶数与偶数之间的相对顺序不变。简单的用类似快排的交换会打乱奇数或者偶数的顺序，所以是行不通的。拜托大家回帖时先把前面的讨论看完。
 
既要时间复杂度为O(n),又不能加辅助数组空间，并且顺序相对不变---难（我目前没想出算法）
 
简而言之就是将A,B而变量互换, 但不定义第三个变量, 故较简单.
A := A+B ;
B := A-B ;
A := A-B ;
 
您必须登录或注册才可回复。

Similar threads

9
急救(面试题)(100分)
2
回复
24
查看
809
94132195
9
A
考高程的朋友请进》》(20分)
回复
5
查看
259
testnet
T
B
对t_sql有兴趣的朋友请加我18963264(0分)
回复
0
查看
81
blues hu
B
9
急救(面试题)(120分)
回复
3
查看
197
94132195
9
W
有兴趣整理Delphi标准函数的朋友进来看看(200分)
2
回复
24
查看
254
wingfly
W
后退
顶部