| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 797 人关注过本帖, 2 人收藏
标题:今天在中国程序员论坛上看到一个题目,大家看看还有没有其它的解法
只看楼主 加入收藏
snailqiu
Rank: 2
等 级:论坛游民
帖 子:59
专家分:45
注 册:2007-9-26
结帖率:100%
收藏(2)
已结贴  问题点数:10 回复次数:8 
今天在中国程序员论坛上看到一个题目,大家看看还有没有其它的解法
题目:输入一个数组,输入结束时打印出排序,如输入的数组为98 82 2 73 80    则输出为
98    1
82    2
2     5
73    4
80    3
以下是楼主的答案:
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
#define MIN 0
int main(void)
{
    int score[MAX+1]={0};
    int juni[MAX+2]={0};
    int count=0,i;
    do
        {
       printf("输入分数,-1结束:");
       scanf("%d", &score[count++]);
    }
        while(score[count-1]!=-1);
    count--;
    for(i=0;i<count;i++)
        juni[score[i]]++;
    juni[MAX+1]=1;
    for(i=MAX;i>=MIN;i--)
        juni[i]=juni[i]+juni[i+1];
    printf("得分\t排行\n");
    for(i=0;i<count;i++)
        printf("%d\t%d\n",score[i],juni[score[i]+1]);
    return 0;
}

下面是我的解法:
#include<stdio.h>
#include<stdlib.h>
void sort(int *pArr,int len);
int main()
{
    int i=0,j=0,k=0,flag=1;
    int *Arr1;//用户输入的数组
    int *Arr2;//再造一个数组
    printf("请依次输入数组的各项(用空格隔开),输入-1时输入结束\n");
    Arr1=(int *)malloc(1*sizeof(int));
   
    while(flag)//此循环为当输入的值不为-1时,将输入结果存储到一个动态数组中
    {
        scanf("%d",&Arr1[i]);
        if(Arr1[i]==-1)
           break;
        else
        {
            Arr1=(int *)realloc(Arr1,1*sizeof(int));//在原来的基础上再动态分配内存
            k++;
            i++;
            flag=1;
        }
    }

 
    Arr2=(int *)malloc(k*sizeof(int)); //再动态构造一个长度为k项的数组   
     for(j=0;j<k;j++)
        Arr2[j]=Arr1[j];//将Arr1赋给Arr1
     sort(Arr2,k);  //对Arr2从大到小进行排序
      printf("得分\t排行\n");   
    for(j=0;j<k;j++)//在一个循环中对这两个数组进行比较
       for(i=0;i<k;i++)
         {
             if(Arr1[j]==Arr2[i])//如果找到了相同的项
               printf("%d\t:%d\n",Arr1[j],i+1);//输出Arr1中相应的项以及Arr2中相应的下标加1
         }
   
   
    return 0;
}
void sort(int *pArr,int len)//从大到小排序
{
    int i,j,t;
   
    for(i=0;i<len-1;i++)
    {
        for(j=0;j<len-1-i;j++)
        {
            if(pArr[j]<pArr[j+1])
            {
                t=pArr[j];
                pArr[j]=pArr[j+1];
                pArr[j+1]=t;
            }
        }
  
    }
}
他用的是定长数组,我用了动态数组。
请大家提提意见。
搜索更多相关主题的帖子: include 程序员 count 中国 
2013-07-14 16:43
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:5 
两码事。

原贴用的是标记法,复杂度是O(n)。不过这种方法的应用有一个条件你没写,不知道原贴里有没有说,那就是数组中元素不能相同。

你的动态数组用的其实不提倡,也不是与人家代码的本质区别。重点在于,你用的是排序,还是冒泡排序,算法复杂度是O(n^2)。

针对这个特定的问题你这效率差很多。

重剑无锋,大巧不工
2013-07-14 18:27
那小扎
Rank: 1
来 自:长沙
等 级:新手上路
帖 子:21
专家分:9
注 册:2013-6-12
收藏
得分:5 
你自己写的有太多的循环和判定,这会浪费太多的时间,个人不喜欢这种使用这种华而不实,意义不大的代码,并不是这道题的一个好的解答,你应该通过一些算法来简化代码,而且我不认为C语言有如此强大功能的动态数组,这简直可以取代链表,而可变长数组也就是VLA,也应该不能如此自由的加长数组,
当然,第一个算法就简洁的多,这毫无疑问可以简单的实现题目要求的功能,它比你自己写的要快的多。

    将编写玩具式程序的趣味性与为实现功能而进行开发的艰难性区分开来!!
2013-07-14 19:28
那小扎
Rank: 1
来 自:长沙
等 级:新手上路
帖 子:21
专家分:9
注 册:2013-6-12
收藏
得分:0 
回复 2楼 beyondyf
第一个算法的复杂度怎么可能会是O(n)纳,有两次循环呀

[ 本帖最后由 那小扎 于 2013-7-14 19:56 编辑 ]

    将编写玩具式程序的趣味性与为实现功能而进行开发的艰难性区分开来!!
2013-07-14 19:33
snailqiu
Rank: 2
等 级:论坛游民
帖 子:59
专家分:45
注 册:2007-9-26
收藏
得分:0 
楼上两位都是高手啊。
其实我学C没多久,算法什么的还不太懂。
非常感谢两位指出我的缺点。
2013-07-14 19:34
那小扎
Rank: 1
来 自:长沙
等 级:新手上路
帖 子:21
专家分:9
注 册:2013-6-12
收藏
得分:0 
回复 5楼 snailqiu
呵,楼上是B大版主,本版每个人都希望自己发的帖子可以被他置顶,你可以关注下动态,他进入的每个帖子都有学习的价值

    将编写玩具式程序的趣味性与为实现功能而进行开发的艰难性区分开来!!
2013-07-14 19:47
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 4楼 那小扎
那两个循环并没嵌套,算法时间复杂度分析是忽略常数因子的。

你帖子中的笔误我就不追究了,但希望改正。

重剑无锋,大巧不工
2013-07-14 19:50
snailqiu
Rank: 2
等 级:论坛游民
帖 子:59
专家分:45
注 册:2007-9-26
收藏
得分:0 
回复 6楼 那小扎
照你这么说,我竟然这么荣幸被他点评了一下。看来我的这个帖子还是有一定的价值的。呵呵
2013-07-14 19:54
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 6楼 那小扎
这么高的评价,谢了。

每个人的侧重点不同,我更关注算法类讨论的帖子。

重剑无锋,大巧不工
2013-07-14 19:55
快速回复:今天在中国程序员论坛上看到一个题目,大家看看还有没有其它的解法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.035491 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved