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

Y

yihanyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #1

一个数组,从1道100,编写一段算法实现数组的奇树排在前,偶鼠排在候,算法时间复杂度0
[135...246...100]
在原数组上作改动，不许另外定义新数组

 

Y

yihanyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #2

一个数组,从1道100,编写一段算法实现数组的奇树排在前,偶鼠排在候,算法时间复杂度0
[135...246...100]
在原数组上作改动，不许另外定义新数组

 

L

Lucker

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #3

自由界面和报表的完美解决方案！
http://www.anylib.com

 

D

Dorice

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #4

很简单吧
#include <iostream>
using namespace std;
void main()
{
int a[100];
int i, j, t;
for (i=0;
i<100;
i++)
{
a = i;
cout<<i<<&quot;
&quot;;
}
cout<<endl;
i=0;
j=99;
while (i<100 &amp;&amp;
j>=0)
{
while (i<100 &amp;&amp;
a%2==0) {
i++;
}
while (j>=0 &amp;&amp;
a[j]%2!=0) {
j--;
}
if (i<100 &amp;&amp;
j>=0) {
t=a;
a=a[j];
a[j]=t;
}
else
break;
i++;
j--;
}
for (i=0;
i<100;
i++)
{
cout<<a<<&quot;
&quot;;
}
cout<<endl;
}

 

Y

yihanyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #5

Dorice：
你的程序的时间复杂度是O？而且，你自己也没有运行过把？
你的结果根本就不对

 

放

放飞

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #6

procedure TForm1.Button1Click(Sender: TObject);
const
conCount = 100;
var
a: array [0..conCount - 1] of Integer;
i: Integer;
n, k: Integer;
begin
//初始化数组
Randomize;
for i := 0 to conCount - 1do
a := Random(1000) + 1;
//排序:奇数在前，偶数在后
k := 0;
for i := 0 to conCount - 1do
begin
if a mod 2 = 1 then
begin
n := a;
a := a[k];
a[k] := n;
k := k + 1;
end;
end;

//输出
Memo1.Lines.begin
Update;
try
Memo1.Clear;
for i := 0 to conCount - 1do
Memo1.Lines.Add(IntToStr(a))
finally
Memo1.Lines.EndUpdate;
end;
end;

 

Y

yihanyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #7

to : 放飞
是这样的：例如原来为：1 2 3 4 5 6 7 8 9 10 ..99 100
输出为：1 3 5 ..99,2 4 6 8 ..96 98 100
你的算法，对于奇数没有问题，但是对于偶数的顺序有问题

 

放

放飞

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #8

你并没有要求要保持原来的顺序啊

 

Y

yihanyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #9

是我没有说清楚，不好意思

 

无

无头骑士

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #10

不需要排序吧？？

 

Y

yihanyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #11

原数组：1 2 3 4 5 6 ...99 100
输出：1 3 5 7 9 ..97 99 2 4 6 8 10 .. 96 98 100

 

S

sdzhaoweiji

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #12

有点困难

 

D

dzl19

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #13

思路:使用冒泡法排序
第一步骤:把偶数排到后面
第二步骤:对奇数排序
第三步骤:对偶数排序

 

放

放飞

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #14

//使用如下的方法，可以对任意大小的数组按照LZ的排序规则排序
procedure jh(pi: PInteger;
n, iCount, iEnd: Integer);
var
tmp: Integer;
pi2: PInteger;
begin
pi2 := pi;
if n mod 2 = 1 then
begin
if iCount mod 2 = 1 then
tmp := (iCount - n) div 2
else
tmp := (iCount - 1 - n) div 2;
Inc(pi2, tmp);
tmp := tmp + n;
if tmp <> iEnd then
jh(pi2, tmp, iCount, iEnd)
end
else
begin
tmp := n div 2;
Dec(pi2, tmp);
if tmp <> iEnd then
jh(pi2, tmp, iCount, iEnd)
end;
if n <> iEnd then
pi2^ := pi^;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
a: array of Integer;
i: Integer;
k: Integer;
iCount: Integer;
begin
try
iCount := StrToInt(Edit1.Text);
except
iCount := 100;
end;
//初始化数组,为了方便计算，第0个数组不用
SetLength(a, iCount);
for i := 0 to iCount - 1do
a := i + 1;
//排序:奇数在前，偶数在后，并保持顺序
i := 1;
while i < ((iCount + 1) div 2)do
begin
if a mod 2 = 0 then
begin
k := a;
jh(@a, i, iCount, i);
if (iCount mod 2) = 0 then
a[i + (iCount - 1 - i) div 2] := k
else
a[i + (iCount - i) div 2] := k;
end;
Inc(i)
end;

//输出
Memo1.Lines.begin
Update;
try
Memo1.Clear;
for i := 0 to iCount - 1do
Memo1.Lines.Add(IntToStr(a))
finally
Memo1.Lines.EndUpdate;
end;
end;

 

A

alllovewg

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #15

//把放飞的改一下
//有问题 改动中

 

网

网事如风

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #16

private void button1_Click(object sender, System.EventArgs e)
{
//int[] AryInt = new
int[] IntAry = new int[99];
for ( int I = 0;
I < IntAry.Length;
I++ )
{
IntAry = I + 1;
}
for ( int I = 0;
I < IntAry.Length;
I++ )
if ( I % 2 == 0)
{
IntAry[ (I + 1 ) / 2 ] = I + 1;
}
else
{
IntAry[ I / 2 + 50 ] = I + 1;
}
}

 

Y

yihanyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-08

• #17

TO:网事如风
我说的输出顺序指的是原数组的下标，至于数组里存的是什么数据就不确定了，所以你的不对

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-09

• #18

如下方法应该可行（无环境，无法编程测试）：
先扫描一遍，统计奇数的个数，记为m。时间O。
然后重新依次扫描数组，对遇到的第i个奇数，与位置i的数交换；第i个偶数，与位置m+i的数交换。时间为O。
总计时间O，完毕。

 

D

d_eng

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-09

• #19

main()
{
int i,j,k;
int a[10]={0};
for (i=0;i<10;i++) scanf(&quot;%d&quot;,&amp;a);
printf(&quot;input data:&quot;
for (i=0;i<10;i++) printf(&quot;%4d&quot;,a);
printf(&quot;/nsorted data:&quot;
for (i=0,j=0;i<10;i++) {
if (a%2!=0){
if (i!=j) {
for(k=i;k>j;k--){
a[k-1]=a[k]^a[k-1];
a[k]=a[k-1]^a[k];
a[k-1]=a[k-1]^a[k];
}
}
j++;
}
}
for (i=0;i<10;i++) printf(&quot;%4d&quot;,a);
printf(&quot;/n&quot;
}

 

E

edgaryu

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-09

• #20

同意AI_Player的算法