每日二题：
每日二题：
1.编一个函数，把数组中最大元素与第一个元素对调。
2.编过程，把整数组中值相同的元素删除得只剩一个；并把剩余元素全部串到前边。（请写出你所能写出的最优算法）
问题点数：10、回复次数：20Top
1 楼loewe（可怜没人爱）回复于 2003-09-03 05:47:07 得分 0
1.
void fun(int a[],int n)//n is the length of the array
{
int max = a[0] , max_pos = 0 , t ;
for(int i = 1 ; i < n ; i++)
{
if(a[i] > max)
{
max = a[i] ;
max_pos = i ;
}
}
t = max ;
a[max_pos] = a[0] ;
a[0] = max ;
return ;
}
Top
2 楼loewe（可怜没人爱）回复于 2003-09-03 05:53:19 得分 0
楼主最近超活跃啊~~~Top
3 楼frankzch（西方失败）回复于 2003-09-03 08:27:26 得分 0
void fun(int a[],int n)//n is the length of the array
{
int temp = a[0] , max_pos = 0 ;
for(int i = 1 ; i < n ; i++)
{
if(a[i] > a[0])
{
a[0]= a[i] ;
max_pos = i ;
}
}
a[max_pos] = temp ;
return ;
}Top
4 楼WYlslrt（WY.lslrt(http://www.wyos.net)）回复于 2003-09-03 08:35:31 得分 1
楼主好活跃呀。Top
5 楼frankzch（西方失败）回复于 2003-09-03 08:56:38 得分 1
void fun(int a[],int n)//n is the length of the array
{
int equal[n],i,j,cur=0;
for(i = 0 ; i < n ; i++)
for(j=i+1;j<n;j++)
if(a[j] ==a[i])equal[j]= 1 ;
else equal[j]=0;
for(i=0;i<n;i++)
if(!equal[i])a[cur++]=a[i];
return ;
}
Top
6 楼xdspower（杂食菜熊）回复于 2003-09-03 09:04:39 得分 1
第一题最简单的是冒泡法（比较 n-1 次），但效率是否最高我就不知道了
第二题原理是比较简单的，就是新产生一个接收数列来接收，当然也可以利用空出的位置。Top
7 楼booming（信誉值由于系统错误导致）回复于 2003-09-03 10:37:39 得分 0
我的建议，代码不一定写，如果你认为简单。
但自己的思想（解题思路）一定要说说。
谢谢大家捧场。Top
8 楼RouteSim（菜鸟飞）回复于 2003-09-03 21:15:58 得分 2
void exchange( int a[],const int n )
{
cout<<"call"<<endl;
int max_pos = 0;
for( int i=0; i<n; i++ )
{
if ( a[max_pos]<a[i] )
{
max_pos = i;
}
}
//开始交换
int temp = a[max_pos];
a[max_pos] = a[0];
a[0] = temp;
}
比较次数好象是不能减少的，那就尽量减少记录移动（严版的数据结构是这样写的）的次数
本函数只进行了3次记录的移动操作（在交换的时候进行的），够不够好？？Top
9 楼loewe（可怜没人爱）回复于 2003-09-03 21:38:20 得分 1
to xdspower()
第二题我觉得应该排序先,然后新产生一个接收数列来接收Top
10 楼RouteSim（菜鸟飞）回复于 2003-09-03 21:42:10 得分 1
第二题我觉得用静态涟表最好；
我是从最坏的时间复杂度的角度考虑的；Top
11 楼xdspower（杂食菜熊）回复于 2003-09-04 07:07:28 得分 1
在接收的时候可以排序来加快以后的搜索比较。Top
12 楼ghost34（风）回复于 2003-09-04 23:41:13 得分 1
对于第一题个人认为还是 frankzch(西方失败) 兄的第一种算法比较好,O(n)
如果用冒泡法0(n^2)
2题我想用插入排序的方法是否能行
Top
13 楼xdspower（杂食菜熊）回复于 2003-09-05 08:42:12 得分 1
由于只选最大值（最小值）不是排序，所以复杂度为O(n)，而不是O(n^2),前面我说了只比较n-1次， frankzch(西方失败)就是冒泡法呀.
2.静态链表没有数组应用方便的，插入排序涉及到数据的大量移动，所以可能效率不高。其实用空间换时间也是比较高的，我有一个比较奇怪的方法，是空间换时间，要求数据是非负整数（在整数比较小时效率比较高），
申请一块十分大的bit数组BIT[LEN]（LEN=MAX整数＋1），扫描一要处理的数组，设置BIT[a[i]]=1;
然后
j=0;
for (i=0;i<LEN;i++) if(BIT[i]==1){a[j]=i;j++;}
这个算法的应用环境是可能整数的最大值<<数组的长度。
Top
14 楼zlf_jack（风云剑客）回复于 2003-09-06 01:09:12 得分 0
第一题，考虑随机分布数组，可知其最优复杂度为0（n)。
第二题，简单算法如下:
for（j＝0，i=0;i++;i<length)
{
if (a[i]=!=maxint)
{
将余下与a[i]相同的赋值为maxint;
j++;
if（i>j)
a[j]=a[i];
}
0（n*n)
改经：
采用B＋树，判断元素是否在树中，不是的话交换到前面！
0（n×log2（n)
0（n）算法还没想出！
Top
15 楼frankzch（西方失败）回复于 2003-09-06 13:34:52 得分 0
我的两个回复一个是第一题的,一个是第二题的,就是名字我懒得改了,但是你们不要以为是一个题目的两种算法,是两个题目(是不是很罗嗦?)Top
16 楼chon81（当我遇上你…）回复于 2003-09-06 14:22:43 得分 0
第一题肯定要遍历一次吧.求最大的数啊.
第二题可以用a[i]跟前面的数比较是不是一样,一样的话,就和最后一个数交换.Top
17 楼xdspower（杂食菜熊）回复于 2003-09-06 20:38:55 得分 0
第二题用我前面的方法，不过另外的数组用哈希表代替可能效率就可以提高，应用环境也加强了。Top
18 楼zhaoxiaoyang（梅雪香@深圳）回复于 2003-09-07 20:48:02 得分 0
for(i=0,j=length;i=j;i++)
{ int k=i+1;
while(k<=j)
{ if(a[i]==a[k])
do{
a[k]=a[j];
j--;
}while(a[k]!=a[j]);
else
k++;
}
}
return a[0..j];
不知道对不对,大家能不能看懂
Top
19 楼hijack（Time timeIsMoney）回复于 2003-09-07 21:47:40 得分 0
第二题感觉和排序有很大关系
Top
20 楼zhoubingg（阿炳）回复于 2003-09-07 22:32:15 得分 0
第一题我觉得用直接选择法效果好一些Top
