一道C语言题目（数字模式的识别），高手来找好算法！小弟我的在OJ上提交要超时

一道C语言题目（数字模式的识别），高手来找好算法！！！！我的在OJ上提交要超时。
Description 数字的模式是指在一堆给定数字中出现次数最多的数值，如5，5，5，3，3，2，6，4，它的模式就是5。现在你的任务，就是从数字中找到它的模式.
Input 第一行为整数N.从第二行开始为N个整数。对于输入的每个数，有( |input_number| <= 2000000 ).
Output 输出这些数字的模式，如果模式个数不为1，选择它们之中较小的。
Sample Input

10
1 2 3 4 5 6 7 8 9 9

Sample Output

9

超时代码：
#include <stdio.h>
int main()
{
int n,str[2000000];//我是先绛序排列，再找
int i,j,a,g=0,b=0,c;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&str[i]);
for(i=0;i<n;i++)
{
for(j=i+1;j<=n;j++)
{
if(str[j]>str[i])
a=str[j],str[j]=str[i],str[i]=a;
else if(str[i]==str[j])
{
g++;
if(g>=b)
{b=g,c=str[i];}
}
else
g=0;
}
}
printf("%d\n",c);
return 0;
}

求好算法啊！！！~~~

[解决办法]
请问N的大小是多少？程序所要求的时间是多少？没有数据范围，没有时间要求？
[解决办法]
输入值的最大值为2000000，开一个2000000*2的int数组，直接hash然后扫描一遍就可以了。O(n)的算法
[解决办法]

引用

#include <stdio.h>
#define N 4000001
int hash[N]; 
int main()
{
int i,n,y,a,max,;
for(i=0;i<N;i++) hash[i] = 0; 
scanf("%d",&n);
for (i = 1 ;i<=n;i++)
{
scanf("%d",&a);
hash[a+2000000]++;
}
max = 0;
for(i =0 ;i< N;i++)
{
if (hash[i] > max ) 
{
max = hash[i];
y = i; 
}
}
printf("%d\n",y-2000000);
return 0;
}

[解决办法]
1.从小到大排序
2.遍历数组，将值相等的放入同一数组，如
数组0：2
数组1：3，3
数组2：4
数组3：5，5，5
数组4：6
3.取出size最大的数组即可，若存在相同size的数组，取数组序号较小者
[解决办法]
你是那个OJ上面的那个题目，地址弄出来，还有上面你写的那个代码
for (i=1; i<=4000000; ++i){
if (b[i] > max){
max = b[i]; max_i = i;
 这个地方的I应从0开始 而不是1
算法的思想是：
将-200万-200万的数字映射到0-400万，因为hash的时候，数组的下标不能使负数。
所以每一个数字都要加200万。


[解决办法]

探讨

引用:

引用
#include <stdio.h>
#define N 4000001
int hash[N]; 
int main()
{
int i,n,y,a,max,;//这里多写了一个‘,’，去掉就可以了，OJ上面有报错信息的，为什么不看看错误原因呢？我去提交了一次，可以通过。
for(i=0;i<N;i++) hash[i] = 0; 
scanf("%d",&amp;amp;n);
for (i = 1 ;i<……

[解决办法]
代码优化了一下
#include <stdio.h>
#include <string.h>
#define N 4000001
int hash[N]; 
int main()
{
int i,n,y,a,max;
scanf("%d",&n);
max = 0;
y = - 2000001;
for (i = 1 ;i<=n;i++)
{
scanf("%d",&a);
if ( ++hash[a+2000000] > max )
{
max = hash[a+2000000];
y = a ;
}
else if ((hash[a+2000000] == max) && (a <= y)){
y = a;
}
}
printf("%d\n",y);
return 0;
}

[解决办法]

C/C++ code

    int count = 18;    int arr[18] = {10, 5, 5, 1, 1,2,3,4,5,6,7,7,8,100,102,123,10,9};        int exchange = 1;    for (int i = 0; i < 17 && exchange; i++)    {        exchange = 0;        for (int j = 0; j< 17-i; j++)        {            if(arr[j] > arr[j+1]){                exchange = 1;                int tmp = arr[j+1];                arr[j+1] = arr[j];                arr[j] = tmp;            }        }    }    int descValue = arr[0];    int descCount = 1;    int descValueTmp = arr[0];    int descCountTmp = 1;    for (int k = 1; k<18; k++)    {        if(descValueTmp == arr[k]){            descCountTmp ++;        }        else{            if(descValue == descValueTmp){                descCount = descCountTmp;            }            else{                if(descCountTmp > descCount){                    descValue = descValueTmp;                    descCount = descCountTmp;                }                else if(descCountTmp == descCount){                    descValue = descValueTmp > descValue ? descValue : descValueTmp;                }            }            descValueTmp = arr[k];            descCountTmp = 1;        }    }    printf("%d", descValue); 
 
[解决办法]
探讨


你是那个OJ上面的那个题目，地址弄出来，还有上面你写的那个代码
for (i=1; i<=4000000; ++i){
  if (b[i] > max){
  max = b[i]; max_i = i;
  这个地方的I应从0开始 而不是1
算法的思想是：
将-200万-200万的数字映射到0-400万，因为hash的时候，数组的下标不能使负数。
所以每一个数字都要加200万……

[解决办法]
[Quote=引用:]

代码优化了一下
#include <stdio.h>
#include <string.h>
#define  N 4000001
int hash[N];  
int main()
{ 
   int i,n,y,a,max;
   scanf("%d",&amp;n);
   max = 0;
   y = - 2000001;
   for (i = 1 ;……
[/Quot]
这个好。 

 

查看更多 下一篇