Manchester-众数问题(帅气实现：如果有多个众数，只输出最小的)

1892 阅读 4 评论 13 点赞

#### 解题思路:
    ①把众数集看做链表，每个结点包括：zhongshu(众数),chongshu(重数)
    ②：每输入一个数x，看它在众数集中是否存在
    ③：若不存在，链表中增加结点
    ④：若存在，zhongshu等于x的结点的chongshu加1
    ⑤：完成输入后遍历链表第一遍，找出最大的重数：max_chongshu
    ⑥：把链表中chongshu小于max_chongshu的结点删除（代码中为了少遍历，采取的方法最后一个结点没有遍历到，后面单独处理）
    ⑦：留下来的结点就是重数相同且重数最大
    ⑧：在剩下的节点中找到最小的众数，输出
#### 参考代码：
```c
#include <stdio.h>
#include <malloc.h>
typedef struct node_ {
    int    chongshu; //重数
    double    zhongshu;//众数

struct node_ *next;
}*node, Node;
/*-----------------------------------------------*/
int search( double x, node head );//查找众数x是否存在

void add_node( double x, node head );//添加众数x

void output( node head );//输出结果

/*-----------------------------------------------*/
int main()
{
    int    n;
    double    x;
    Node    Head;
    Head.next = NULL;
    scanf("%d",&n);
    for ( int i = 0; i < n; i++ )
    {
        scanf( "%lf", &x );
        if ( search( x, &Head ) == 0 )
        {
            add_node( x, &Head );
        }
    }

output( &Head );
    return(0);
}

/*-----------------------------------------------*/
int search( double x, node head )
{
    int    term    = 0;
    node    p    = head->next;

while ( p != NULL )
    {
        if ( x == p->zhongshu ) //找到众数，已存在
        {
            p->chongshu++;
            term = 1;
            break;
        }
        p = p->next;
    }

return(term);
}

/*-----------------------------------------------*/
void add_node( double x, node head )//添加众数x
{
    node q = (node) malloc( sizeof(Node) );

q->chongshu    = 1;
    q->zhongshu    = x;

q->next        = head->next;  //前插法
    head->next    = q;

return;
}

/*-----------------------------------------------*/
void output( node head )
{
    node p = head->next;
    if ( p == NULL ) //链表为空，则返回
        return;
        //求最大重数：max_chongshu
    int max_chongshu = p->chongshu;

while ( p != NULL )
    {
        if ( max_chongshu < p->chongshu )
            max_chongshu = p->chongshu;

p = p->next;
    }
/* delete删除 chongshu小于max_chongshu 的结点 ---------------------------------*/
    //删除方法找一个删除一个，只遍历一遍，故指针q只指向被删除结点的前一个，最终尾结点没遍历到
    node    q    = head;
    node    d    = NULL;
    while ( q->next != NULL )
    {
        if ( q->next->chongshu < max_chongshu )
        {
            d    = q->next;
            q->next = q->next->next;
            free( d );
        }else
            q = q->next;
    }
    /*-----------------------------*/
    //判断尾结点chongshu，小于max_chongshu则删除
    node h = head;
    while ( h->next != q )
        h = h->next;

if ( q->chongshu < max_chongshu )
        h->next = q->next;
    free( q );
    /*------------------------------*/
    //在chongshu相同且为最大的节点中，找到最小的众数输出
    q = head->next;
    double min_zhongshu = q->zhongshu;
    while ( q != NULL )
    {
        if ( q->zhongshu < min_zhongshu )
            min_zhongshu = q->zhongshu;
            q=q->next;
    }

printf( "%.0lf\n", min_zhongshu );//输出众数
    printf( "%d", max_chongshu );//输出重数
}
```

#### 解题思路2：
    设输入的数字集为num{8,9,7,8,9,9,9,6,8,9,7,7,2,1,1,2,6}
    从小到大排序后为num1{1,1,2,2,6,6,7,7,7,8,8,8,9,9,9,9,9}
显然发现众数为9，因为观察9最长，更具这个特点我们把题目转化为：给定一个数字集，如上mun1，其中数字满足从小到大的排序，求其中重复出现次数最多的数字，以及出现的次数。
#### 参考代码：代码思路来自1402:简单字符串
```c
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
int comp(const void *value1, const void *value2) {
	// 升序
	return (*(int*)value1 - *(int*)value2);
}
int main()
{
    int n,Startpos,Length,ii,jj;
    int *num;
    while(scanf("%d",&n)!=EOF)
    {
       num=(int *)malloc(n*sizeof(int));//开辟空间
       for(int i=0;i<n;i++)
          scanf("%d",&num[i]);
       //从小到大排序
       qsort(num,n,sizeof(int),comp);
       Length=0;
       ii=0;
       for(int i=0;i<n;i++)
       {
           if(num[i]!=num[i+1])
           {
               jj=i;//第一个可能的众数结束位置
               if(jj-ii+1>Length)
               {
                   Length=jj-ii+1;//更新众数重数
                   Startpos=ii;//更新众数下标
               }
               ii=i+1;//新的可能是众数的下标
           }
       }
      printf("%d\n",num[Startpos]);
      printf("%d\n",Length);
      free(num);
    }
}

```

0.0分

3 人评分

本文分类：题解列表
浏览次数：1892 次浏览
发布日期：2018-03-06 23:05:33
本文链接：https://blog.dotcpp.com/a/5983

上一篇 > C语言程序设计教程（第三版）课后习题6.8 （C语言代码）
下一篇 > 蓝桥杯历届试题-分糖果（C++代码）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

Manchester-众数问题(帅气实现：如果有多个众数，只输出最小的)

评论列表共有 4 条评论

发表评论取消回复

Manchester-众数问题(帅气实现：如果有多个众数，只输出最小的)

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 4 条评论

发表评论 取消回复

评论列表共有 4 条评论

发表评论取消回复