poj2092 简单排序

妖狐艹你老母 2021-12-17 02:57 87阅读 0赞

我的思路: 先把每个数的出现的次数和下标记录，所以用到一个数据结构Node\{num,points\}。然后先根据points值排序，那么node\[0\].points就是最大值，然后我们就可以得到第二大的值，和他的位置，然后再把第二大的值的num排序一下，就可以输出了。因为我不想用那么多次for循环，所以用了两次排序。其实这题也可以用三次for来求出，但事先要先求出最大值和第二的的值。我比较了下，简单的for和我的这种方法，我的是150+ms，那个是200ms。 还是快一点点的，哈哈

![2012042013010262.png][]

#include <iostream>
    #include <cstdlib>
    #include <fstream>
    
    using namespace std;
    #define MAX 10001
    
    typedef struct
    {
        int num;
        int points;  //出现的次数
    }Node;
    Node node[MAX];
    
    int cmp(const void *a,const void *b)  //降序排列
    {
        return ((Node*)b)->points-((Node*)a)->points;
    }
    
    int cmp1(const void *a,const void *b)
    {
        return ((Node*)a)->num-((Node*)b)->num;
    }
    
    int main()
    {
        int n,m,i,maxn,nums,index,nCount;
        freopen("acm.txt","r",stdin);
        while( scanf("%d%d",&n,&m)!=EOF && n+m)
        {
            for(i=0; i<MAX; i++)
            {
                node[i].num=0;
                node[i].points=0;
            }
            for(i=0; i<n*m; i++)
            {
                    scanf("%d",&nums);
                    if(node[nums].num!=nums)
                    {
                        node[nums].num=nums;
                    }    
                    node[nums].points++;
            }
             //根据points排序
            qsort(node,MAX,sizeof(Node),cmp); 
             maxn=node[0].points;  //第一大的points值
               i=1;
              while(node[i].points==maxn)
              {
                  i++;
              }
              //确定第二大的位置
              index=i;  //第二大的第一个位置
              maxn=node[i].points;  //记录第二大的points值
              nCount=0;
              while(node[i].points==maxn)
              {
                 nCount++;
                  i++;
              }
              //把排第二的排序一下
              qsort(node+index,nCount,sizeof(Node),cmp1);
              while(nCount--)
              {
                  printf("%d ",node[index++].num);
              }
              printf("\n");
         }
            return 0;
    }

转载于:https://www.cnblogs.com/Jason-Damon/archive/2012/04/20/2459147.html

[2012042013010262.png]: /images/20211214/17af07e9f7164dc1bc73cfe4445ab283.png