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

  • 主题发起人 主题发起人 yihanyan
  • 开始时间 开始时间
Y

yihanyan

Unregistered / Unconfirmed
GUEST, unregistred user!
一个数组,从1道100,编写一段算法实现数组的奇树排在前,偶鼠排在候,算法时间复杂度0(n)
[135...246...100]
在原数组上作改动，不许另外定义新数组
 
一个数组,从1道100,编写一段算法实现数组的奇树排在前,偶鼠排在候,算法时间复杂度0(n)
[135...246...100]
在原数组上作改动，不许另外定义新数组
 
自由界面和报表的完美解决方案！
http://www.anylib.com
 
很简单吧
#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;
}
 
Dorice：
你的程序的时间复杂度是O(n)？而且，你自己也没有运行过把？
你的结果根本就不对
 
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;
 
to : 放飞
是这样的：例如原来为：1 2 3 4 5 6 7 8 9 10 ..99 100
输出为：1 3 5 ..99,2 4 6 8 ..96 98 100
你的算法，对于奇数没有问题，但是对于偶数的顺序有问题
 
你并没有要求要保持原来的顺序啊
 
是我没有说清楚，不好意思
 
不需要排序吧？？
 
原数组：1 2 3 4 5 6 ...99 100
输出：1 3 5 7 9 ..97 99 2 4 6 8 10 .. 96 98 100
 
有点困难
 
思路:使用冒泡法排序
第一步骤:把偶数排到后面
第二步骤:对奇数排序
第三步骤:对偶数排序
 
//使用如下的方法，可以对任意大小的数组按照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;
 
//把放飞的改一下
//有问题 改动中
 
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;
}
}
 
TO:网事如风
我说的输出顺序指的是原数组的下标，至于数组里存的是什么数据就不确定了，所以你的不对
 
如下方法应该可行（无环境，无法编程测试）：
先扫描一遍，统计奇数的个数，记为m。时间O(n)。
然后重新依次扫描数组，对遇到的第i个奇数，与位置i的数交换；第i个偶数，与位置m+i的数交换。时间为O(n)。
总计时间O(n)，完毕。
 
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;);
}
 
同意AI_Player的算法
 
您必须登录或注册才可回复。

Similar threads

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