找出数组中重复次数最多的元素并打印 - webdancer's Blog

找出数组中重复次数最多的元素并打印

webdancer posted @ 2011年3月19日 19:02 in 算法 with tags 算法 排序 , 5433 阅读

    题目:找印。

这道题其实在做汇编实验时,已经做过了。但是当时的思路还是太简单,现在又想了一下,可以先排序,然后遍历。这样如果采用快排,时间复杂度应为:O(nlogn+n)。代码:

 

#include<stdio.h>
#include<stdlib.h>

int int_compare(const void * x1,const void * x2){
	int * a=(int *)x1;
	int * b=(int *)x2;
	return (*a-*b);
}

void findremax(int a[],int n,int *m,int *c){
	int index,count,maxc,i;

	index=0;
	count=1;
	maxc=count;
	//printf("%d\n",(sizeof a )/(sizeof a[0])); Error
	for(i=1;i<n;i++){
		if(a[i]==a[i-1])
			count++;
		else{
			if(count>maxc){
				maxc=count;
				index=i-1;
			}
			count=1;
		}
	}
	if(count>maxc){
		maxc=count;
		index=i-1;
	}

	*m=index;
	*c=maxc;
	
}

int main(){
	int maxindex,c;
	int a[]={1,1,2,2,3,3,3,3,4,5,6,7,7,7,7,7,7};
	int n=(sizeof a)/(sizeof a[0]);
	maxindex=0;
	c=0;
	qsort(a,n,sizeof(a[0]),int_compare);
	findremax(a,n,&maxindex,&c);
	printf("%d appears %d times.\n",a[maxindex],c);

	return 0;
}

总结:1.排序的应用,排序可以用来对相同的元素分类,使他们相邻,从而解决问题。

         2.语言问题:在代码中注释掉的://printf("%d\n",(sizeof a )/(sizeof a[0])); Error。没有注意到:在函数中,a是个指针,而不是数组,分了错误,所以:在32位的机器上:(sizeof a )/(sizeof a[0])=1。

Avatar_small
pf_d 说:
2012年5月26日 14:20

直接利用散列表应该可以吧.
唉,我感觉利用C语言写的代码怎么看不懂呢,我比较喜欢用C++.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee