最新文章:

首页 2)SwustOj

寻找出现次数最多的数(1231)

发布时间:2017年11月20日 评论数:抢沙发 阅读数:340

     

    给定n个正整数,找出它们中出现次数最多的数。如果这样的数有多个,请输出其中最小的一个。
    Description
    输入的第一行只有一个正整数n(1 ≤ n ≤ 1000),表示数字的个数。 
    输入的第二行有n个整数s1, s2, …, sn (1 ≤ si ≤ 10000, 1 ≤ i ≤ n)。相邻的数用空格分隔。
    Input
    输出这n个次数中出现次数最多的数。如果这样的数有多个,输出其中最小的一个。
    Output
    1
    2
    6
    10 1 10 20 30 20
    Sample Input
    1
    10
    #include<stdio.h>
    int main()
    {
    	int n;
    	int a;
    	int str[10005]={0};
    	scanf("%d",&n);
    	for(int i=0;i<n;i++)
    	{
    		scanf("%d",&a);
    		str[a]++;
    	}
    	int sum=str[1];
    	int j=1;
    	for(int i=1;i<10001;i++)
    	{
    		if(sum<str[i])
    		{
    			sum=str[i];
    			j=i;
    		}
    	}
    	printf("%d",j);
    	return 0;
    }

    经典排序算法 - 桶排序Bucket sort


    补充说明三点

    1,桶排序是稳定的

    2,桶排序是常见排序里最快的一种,比快排还要快…大多数情况下

    3,桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法


    我自己的理解哈,可能与网上说的有一些出入,大体都是同样的原理

    无序数组有个要求,就是成员隶属于固定(有限的)的区间,如范围为[0-9](考试分数为1-100等)

    例如待排数字[6 2 4 1 5 9]

    准备10个空桶,最大数个空桶

    [6 2 4 1 5 9]           待排数组

    [0 0 0 0 0 0 0 0 0 0]   空桶

    [0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

     

    1,顺序从待排数组中取出数字,首先6被取出,然后把6入6号桶,这个过程类似这样:空桶[ 待排数组[ 0 ] ] = 待排数组[ 0 ]

    [6 2 4 1 5 9]           待排数组

    [0 0 0 0 0 0 6 0 0 0]   空桶

    [0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

     

    2,顺序从待排数组中取出下一个数字,此时2被取出,将其放入2号桶,是几就放几号桶

    [6 2 4 1 5 9]           待排数组

    [0 0 2 0 0 0 6 0 0 0]   空桶

    [0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

     

    3,4,5,6省略,过程一样,全部入桶后变成下边这样

    [6 2 4 1 5 9]           待排数组

    [0 1 2 0 4 5 6 0 0 9]   空桶

    [0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

     

    0表示空桶,跳过,顺序取出即可:1 2 4 5 6 9

     

二维码加载中...
本文作者:行者      文章标题: 寻找出现次数最多的数(1231)
本文地址:http://blog.20a.top/?post=156
版权声明:若无注明,本文皆为“我的小世界”原创,转载请保留文章出处。