众数问题（分治方法解决） |
您所在的位置：网站首页 › 计算机求众数 › 众数问题（分治方法解决） |
众数问题（分治方法解决）
|
众数问题（分治方法解决）
问题描述算法思路与代码实现方法一：排序遍历法代码1：排序遍历法方法二：分治法代码2：分治法
代码测试算法心得和复杂度分析
问题描述
给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中最大的元素称为众数。给定一个n个自然数组成的多重集合S，设计算法求其众数和重数。 题目源于：王晓东.《计算机算法设计与分析》.第5版习题2-14 例如：给出 S = [ 1 , 2 , 3 , 4 , 5 , 2 ] S = [1,2,3,4,5,2] S=[1,2,3,4,5,2] 其众数是2，重数是2 算法思路与代码实现 方法一：排序遍历法将多重集合S中的元素存入一个整型数组当中，对该数组进行排序。排序后，数组相同的元素都会相邻出现。遍历整个数组，记录在遍历过程中记录各个元素及其重数，其中重数最大的元素便是要求得的众数。 具体算法实现思路用以下伪代码说明： int n; scanf("%d",&n); //记录集合的总元素个数 int *arr = scanf(arr); //输入集合元素 Quick_Sort(arr,n,0,n-1);//对集合元素进行排序（这里是快速排序） // 遍历数组找众数 int z=-1,c=-1;//最终的众数，重数 (假设元素都是正数) int zt=-1,ct=-1;//临时众数和重数 (假设元素都是正数) //遍历数组，用类似打擂台法的方法最大的重数和其对应的众数 for(i->1~n){ if(arr[i]!=zt){ //发现新元素时记录下来，同时记录他的重数 zt = arr[i]; ct = 1; }else if(arr[i]==zt){//排序后相同元素都相邻，如果还是旧元素，增加其记录的重数。 ct++; } if(ct>c){ // 如果最大重数的值发生改变，则记录下来。（类似打擂台） c = ct; z = zt; } } printf(z,c);// 输出结果 代码1：排序遍历法 #include #include // standard_library //快速排序 int Quick_Sort(int *data,int data_lenth,int low,int high){ if(low while(low2=pkey)high2--; data[low2] = data[high2]; while(low2 scanf("%d",&arr[i]); } Quick_Sort(arr,n,0,n-1); int z=-1,c=-1;//众数，重数 int zt=-1,ct=-1;//临时众数和重数 ， 打擂台法 for(int i=1;i zt = arr[i]; ct = 1; }else if(arr[i]==zt){ ct++; } if(ct>c){ c = ct; z = zt; } } printf("---------\n%d\n%d\n",z,c); return 0; } 方法二：分治法同样将多重集合S中的元素存入一个整型数组当中，采用分治的思想，选取一个基准数，将比基准数小的放于左侧，比基准数大的放与右侧（类似于一轮快速排序）。此时比较左部分重数最大的数，右部分重数最大的数，基准数的重数这三个数，其中重数最大的便是整个集合S的众数。这样一来，原问题就得到了分解，可以采用分治法写递归函数求解。 |
具体算法实现思路用以下伪代码说明：【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |