重数与众数
- 什么是重数与众数
给定含有N个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数,多重集合S中重数最大的元素称为多重集合S的众数,众数的重数称为多重集合S的重数,试求一个给定多重结合的重数和众数;
例如:S={a,b,b,b,f,f,4,5}的重数是3,众数是b - 基本思路:
采用变治的思想,首先进行预排序,然后通过一次遍历记录所有数据出现的次数,以及最大的一组。 - 算法
PRESORT (array): QUICKSORT (array, 0, size-1) COUNTMODE (array, result): //预排序 PRESORT (array) //modes用于记录所有数据以及其出现次数 modes = modes∪{
array[0]} //j用于记录数据在modes中的位置 j=0, max0 //将第一个数据添加入结果集 result = result∪{
array[0]} for i=1-(size-1) //当前数据和modes中的数据相等,次数加一 if array[i]==modes[j] result[j].num = result[j].num+1 //否则为modes添加新的数据 else modes = modes∪{
array[i]} //当最大次数小于modes[j]的次数,就修改max,以及result if modes[max]<modes[j] max=j result = {
modes[j]} //当最大次数相同,则扩大result集 else result = result∪{
modes[j]} j++
讯享网
- 复杂度:O(nlogn)
预排序复杂度O(nlogn),计数复杂度O(n) - 运行截图
- 源代码
说明:代码分为三部分,预排序、计数、辅助函数
讯享网#include <iostream> #include <vector> #include <ctime> using namespace std; //众数Mode:用于记录值以及出现次数 class Mode{
public: int value; int num=0; Mode(int v) {
value=v; num++; } Mode(const Mode &m) {
value = m.value; num=m.num; } }; //计算重数及众数 //输入数据集以及空的结果集,输出 void CountMode(vector<int> &list,vector<Mode> & result); //快速排序 void QuickSort(vector<int> &list, int left, int right); int Partition(vector<int> &list, int left, int right); void swap(vector<int> &list, int a, int b); void Print(vector<Mode> modes); void GetRandList(vector<int> &list, int n); void Print(vector<int> list); void PrintMode(const vector<Mode> &modes); int main(int argc, char** argv) {
vector<int> list; GetRandList(list,20); Print(list); vector<Mode> modes; CountMode(list,modes); PrintMode(modes); return 0; } void swap(vector<int> &list, int a, int b) {
int temp = list[a]; list[a] = list[b]; list[b] = temp; } int Partition(vector<int> &list, int left, int right) {
int pivot = list[right]; int i=left-1; for(int j=left;j<right;j++) {
if(list[j]<=pivot) {
i++; swap(list,i,j); } } swap(list,i+1,right); return i+1; } void QuickSort(vector<int> &list, int left, int right) {
if(left<right) {
int partition = Partition(list,left,right); QuickSort(list,left,partition-1); QuickSort(list,partition+1,right); } } void Print(vector<Mode> modes) {
for(int i=0;i<modes.size();i++) {
cout<<modes[i].value<<" 次数:"<<modes[i].num<<endl; } } void CountMode(vector<int> &list,vector<Mode> & result) {
QuickSort(list,0,list.size()-1); vector<Mode> modes; modes.push_back(Mode(list[0])); result.push_back(list[0]); int max_index=0; for(int i=1,j=0;i<list.size();i++) {
if(modes[j].value==list[i]) {
modes[j].num++; } else {
modes.push_back(Mode(list[i])); if(modes[max_index].num<modes[j].num) {
max_index=j; result.clear(); result.push_back(modes[j]); } else if(modes[max_index].num==modes[j].num) result.push_back(modes[j]); j++; } } Print(modes); } void GetRandList(vector<int> &list, int n) {
list.resize(n); for(int i=0;i<n;i++) {
list[i] = rand()%n; } } void Print(vector<int> list) {
for(int i=0;i<list.size();i++) {
cout<<list[i]<<" "; } cout<<endl; } void PrintMode(const vector<Mode> &modes) {
for(int i=0;i<modes.size();i++) {
cout<<"众数:"<<modes[i].value<<" 次数:"<<modes[i].num<<endl; } }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/79097.html