-
2019-09-16 20:52:11
众数问题(分治法)
Time Limit: 2000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如,S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。对于给定的由n 个自然数组成的多重集S,计算S的众数及其重数。如果出现多个众数,请输出最小的那个。
Input
输入数据的第1行是多重集S中元素个数n(n<1300000);接下来的n行中,每行有一个最多含有5位数字的自然数,。
Output
输出数据的第1行给出众数,第2行是重数。
Sample Input
6
1
2
2
2
3
5
Sample Output
2
3**代码如下
#include <stdlib.h>
#include <stdio.h>
#include <string.h>int main()
{ int n;
scanf("%d",&n);
int a[n];
int b[99999] = {0};
for(int i = 0;i <n; i++){
scanf("%d",&a[i]);
b[a[i]]++;
}
int maxnum = 0;
int num = 0;
for(int i = 99999; i>=0; i–){
if(b[i] >= maxnum){
maxnum = b[i];
num = i;
}
}
printf("%d\n%d",num,maxnum);
return 0;
}更多相关内容 -
使用分治法解决众数问题
2011-11-05 19:37:37这个程序使用分治法算法思想,求得一组数中的众数,众数的重数。 -
众数问题【分治算法】
2020-12-21 13:58:10多重集S中重数最大的元素称为众数。例如,S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。对于给定的由n 个自然数组成的多重集S,计算S的众数及其重数。如果出现多个众数,请输出最小的那个。 Input 输入数据...给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如,S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。对于给定的由n 个自然数组成的多重集S,计算S的众数及其重数。如果出现多个众数,请输出最小的那个。
Input
输入数据的第1行是多重集S中元素个数n(n<1300000);接下来的n行中,每行有一个最多含有5位数字的自然数,。
Output
输出数据的第1行给出众数,第2行是重数。Sample Input
6 1 2 2 2 3 5
Sample Output
2 3
该问题就是求一个集合最小众数的问题。
#include <bits/stdc++.h> using namespace std; int main() { int n; int mode; //众数 int Max=INT_MIN; //众数的重数,因为要求最大值,故初始化为最小值 int times[10000000]; //用于记录多重集合S中每个元素出现的次数。注意:多重集S中可能只有一个元素,因此该元素的重数为 n cin>>n; while(n--) { int x; //多重集合S中的元素 cin>>x; times[x]++; //元素 x 的出现次数加一 if(Max<times[x]) //如果当前众数的重数小于元素 x 的出现次数,说明 x 为众数 { mode=x; //更新众数 Max=times[x]; //更新众数的重数 } else if(Max==times[x]) //如果当前众数的重数等于元素 x 的出现次数,说明两个数都是众数,这时需要选出最小的那个 { if(x<mode) mode=x; } } cout<<mode<<endl<<Max<<endl; return 0; }
-
分治法之众数求解问题
2012-12-25 16:32:06该资源是关于算法设计的,是文档,但是有附加了代码。 -
分治法-求解众数问题Java
2021-09-22 16:16:571.众数问题: 给定含有N个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数,多重集合S中重数最大的元素称为多重集合S的众数,众数的重数称为多重集合S的重数,试求一个给定多重结合的重数和众数。 例如...1.众数问题:
给定含有N个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数,多重集合S中重数最大的元素称为多重集合S的众数,众数的重数称为多重集合S的重数,试求一个给定多重结合的重数和众数。
例如:S={a,b,b,b,f,f,4,5}的重数是3,众数是b
2.算法思路:
- 首先为集合S排序,使之成为有序的数组(使用Arrays类的sort方法)
- 取中位数为众数,中位数的个数为重数,确定左右界
- 向左界递归,取中位数为众数,取中位数个数为重数,比较
- 向右界递归,取中位数为众数,取中位数个数为重数,比较
3.问题:
翻阅网上的代码,多是使用c++实现,而c++代码中有引用参数传递的过程,在程序运行中可以直接引用函数传参,但Java中没有提供。在阅读(7条消息) 分治法-众数问题java实现_cook_1996的博客-CSDN博客 这篇博客后,发现了IntHolder这个类。
IntHolder持有者类型:因为java中只存在值传递,同时包装类一旦创建其数值是不能改变的。所有不可能实现一个方法改变一个数据类型的值。如果想编写一个修改数据值参数的方法,就需要使用在 org.omg.CORBA 包中定义的持有者(holder)类型,包括IntHolder、BooleanHolder等。每个持有者类型都包含一个共有域值,通过它可以访问储存在其中的值。
4.代码:
import jdk.nashorn.internal.runtime.regexp.joni.encoding.IntHolder; import java.lang.reflect.Array; import java.util.Arrays; import java.util.Scanner; public class Mode { public static void getMaxCnt(int a[], int n, IntHolder num, IntHolder maxCnt){ int l =0, r = 0; int s; int mid = n / 2; for( l = 0;l < mid;l ++){ if(a[l] == a[mid]) break; } for(r = mid + 1;r < n;r ++){ if(a[r] != a[mid]) break; } s = r - l; if(s > maxCnt.value){ num.value = a[mid]; maxCnt.value = s; } if(s == maxCnt.value){ if(num.value > a[mid]){ num.value = a[mid]; maxCnt.value = s; } } if(l + 1 > maxCnt.value){ getMaxCnt(a,l+1,num,maxCnt); } if(n - r > maxCnt.value){ int [] b = new int[n-r]; for(int i = 0;i < n-r;i ++){ b[i] = a[r + i]; } getMaxCnt(b,n-r,num,maxCnt); } } public static void main(String[] args) { int i,n; IntHolder num = new IntHolder(); IntHolder maxCnt = new IntHolder(); System.out.println("请输入数组个数:"); Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); int []a = new int[n]; System.out.println("请输入一个数组:"); for(i = 0;i < n;i ++){ a[i] = scanner.nextInt(); } Arrays.sort(a); getMaxCnt(a,n,num,maxCnt); System.out.println("众数:" + num.value + " 重数:" + maxCnt.value); } }
-
众数问题(分治法)
2019-03-22 11:07:52众数问题 Time Limit: 2000 ms Memory Limit: 65536 KiB Problem Description 给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如,S={1,2,2,2,3,5...众数问题
Time Limit: 2000 ms Memory Limit: 65536 KiBProblem Description
给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如,S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。对于给定的由n 个自然数组成的多重集S,计算S的众数及其重数。如果出现多个众数,请输出最小的那个。Input
输入数据的第1行是多重集S中元素个数n(n<1300000);接下来的n行中,每行有一个最多含有5位数字的自然数,。Output
输出数据的第1行给出众数,第2行是重数。Sample Input
6
1
2
2
2
3
5
Sample Output
2
3
Hint
Source这个题,我的算法思想就是排序,然后找出数组最中间的那个数来,然后用for循环向左向右找和这个数相同的,用变量cnt进行计数,看看有多少个,如果不相同,退出循环,并保存左边和右边的下标i,j。此时,判断左边剩余的元素个数是否大于现在众数的重数,如果大,则继续递归,右边同理。
#include <iostream> #include <bits/stdc++.h> using namespace std; int maxsum,zhongshu,n; void zhong(int a[],int l,int r) { int center = (l + r) / 2; int i,j; int cnt = 1; for(i = center-1; i >= l ; i--) { if(a[i] == a[center]) { cnt++; } else break; } for(j = center+1; j <= r; j++) { if(a[j] == a[center]) cnt++; else break; } if(cnt == maxsum && zhongshu > a[center]) //若相等,则元素小的优先 { maxsum = cnt; zhongshu = a[center]; } if(cnt > maxsum) { maxsum = cnt; zhongshu = a[center]; } if(i-l > maxsum) //若左边剩余元素还大于重数,则有可能会存在更大的众数重数,递归寻找 { zhong(a,l,i); } if(r-j > maxsum) //右边同理 zhong(a,j,r); } int main() { cin>>n; int a[n+9]; for(int i = 0; i < n; i++) cin>>a[i]; maxsum = zhongshu = 0; sort(a,a+n); zhong(a,0,n-1); cout<<zhongshu<<endl; cout<<maxsum<<endl; }
-
分治法求众数问题 (配图)
2021-02-01 01:23:28标签:采用分治法,以中间为界限, 先计算围绕中间这个数字的众数情况,然后左右分开递归计算结果,取最值即可。左右递归计算的时候要先做判断,假如左边或是右边的个数都比已求的重数小,就没必要计算了,即使左边... -
分治算法解决众数问题
2020-07-05 20:19:35多重集s中重数最大的元素称为众数,如s = {1,2,2,2,5,3}。多重集s的众数是2,其重数为3。 分析: 先用快速排序给数组从小到大排好序,接着找出中位数,(元素个数除2就是它的位置),以中位数为参考点,找出中位数... -
分治法——众数问题
2020-01-10 20:04:47分治法——众数问题 给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。 多重集S中的最大元素称为众数。 文件输入: 第一行:多重集合S的个数 接下来的每一行输入S集合中的值 输出: 第一行... -
分治法求众数问题
2019-03-26 21:51:37读完问题我们发现起始求众数就是求一个数组里面出现最多的数及其出现的次数,那么我们与其从左往右依次寻找还不如直接从中间往左右寻找更轻松,假设我们先求出中位数的重数,如果发现左边的数的个数小于这个重数那么... -
分治算法---众数问题java
2022-03-29 20:01:03众数问题 问题描述: 给定含有n个元素的多重集合s,每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如, S-(1, 2, 2, 2, 3, 3, 5).多重集S的众数是2,其重数为3,对于给定的由n个自然数... -
分治法实现众数问题
2016-10-23 22:42:03众数问题(分治法) 问题描述:给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数,多重集合S中重数最大的元素称为众数。例如,S={1, 2 ,2 ,2 ,3 ,5}。多重集合S的众数是2,其重数为3。算法... -
众数问题(分治法求解-mtzhang)
2016-10-30 13:12:56一、问题描述 给定含有n个元素的多重集合s,每个元素在s中出现的次数称为该元素的重数,多重集s中重数最大 的元素称为众数,给定多重集合s,求s中的众数集重数。 二、算法思想及描述 我在网上看了,感觉都晦涩难懂,... -
众数问题-递归和分治
2021-06-04 08:35:53例如:1 2 2 2 3 5众数是: 2算法思路:先排序 后用分治法计算求解分治法求解代码如下:#include #include #include using namespace std;/*----------快速排序*/int Partition(int *a , int l , int r){int i = l , ... -
关于分治求众数和分治求幂时间复杂度的分析
2019-06-21 16:33:11记录一下第一次写CSDN,最近刚看了算法与数据结构的相关视频,其中看到了分治求众数和分治求幂的视频后对它们的时间复杂度的不同产生了强烈的探知欲,在看了一些博客后,根据知识和代码,算是明白了它们的不同。... -
分治算法求众数
2019-09-30 10:37:12一.题目描述: 给定含有n个元素的多重集合S,每个元素在S中出现的次数...算法分析: 首先请求两个全局变量,用来存放不同数字的重数(a数组)和众数(b数组)。将一组数据先排序,再找出一组数据中的中位数,利... -
分治算法--众数问题
2019-10-23 20:16:53多重集S中重数最大的元素称为众数。例如,S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。对于给定的由n 个自然数组成的多重集S,计算S的众数及其重数。如果出现多个众数,请输出最小的那个。 Input 输入... -
分治法求数组中的众数和时间复杂度分析
2020-03-22 18:32:10这是我们算法作业的一个习题,记录一下 #include <stdio.h> int n = 0 ; //存储众数 int s = 0 ; //存储众数的重数 int count(int a[], int p, int q){//计算中位数在数组中的重复次数 int m = a[(p+q)/2] ... -
c语言分治法求众数重数-五大常见算法策略之——递归与分治策略,算法数据结构
2022-04-07 17:39:44c语言分治法求众数重数-五大常见算法策略之——递归与分治策略,算法数据结构 五大常用算法 -
最大值问题 众数问题 (二分法)分治策略实验
2022-05-15 19:53:593. 通过编程实现最大值问题和众数问题,进一步理解分治法中递归的使用方法及分治合的基本步骤。 2、实验内容 1. 最大值问题:给定n个整数,用分治法找出其中的最大值。 两个测试用例:输入数据分别由文件名为 ... -
算法分析与设计:众数问题(C++,分治法)
2019-10-16 15:59:21问题描述:给定含有n个元素的多重集合S,每个元素在S中出现的...算法设计:对于给定的由n个自然数组成的多重集S,计算S的众数及其重数。S有序。 #include <iostream> using namespace std; int larg... -
算法实验二 分治法 众数问题.pdf
2021-01-12 04:15:37算法实验二 分治法 众数问题算法分析与设计实验二分治法主要内容• 实验目的• 主要实验仪器设备和环境• 实验内容• 实验要求• 注意点实验目的• 理解分治法的基本思想• 针对特定问题,可以设计出分治算法进行... -
算法准备-分治算法解决众数求解问题
2021-06-01 13:20:18算法准备-分治算法解决众数求解问题 -
算法:分治法寻找众数
2021-11-30 09:34:51注意:快速排序之后相同的数组元素是相邻的。 #include using namespace std;... cout众数的个数:"; return 0; } int main(){ int a[10] = {1,2,3,4,5,6,7,8,9,9}; Quick_Sort(a,0,9); count_num(a,10); return 0; } -
分治法求众数.doc
2020-11-23 09:37:13算法设计与分析课内实验——分治法求众数。文档很齐全,包括算法分析过程和源代码(java语言eclipse环境) -
分治法与递归---众数问题
2021-10-16 08:26:01分治法基本思想: 将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立(区别于动态规划)且与原问题相同。递归解决这些子问题,然后将各子问题的解合并(不存在相互利用)得到原问题的解。下面以求... -
分治法求众数在C++中的实现
2021-11-20 00:43:31分治法求众数在C++中的实现 问题分析 该问题解决的是求解一串数组中的众数问题。...实际上在我们学习分治法的例题的时候应该也发现,对于分治法的算法设计要尽量使子问题的规模完全相等,实现平衡子问题的 -
寻找众数_分治法
2021-04-08 19:42:07C语言 众数问题 分治法 解题思路: ①排序:拿到一个乱序的数列,先排序(顺序跳过这一步) ②找中位数 ③ 遍历:得到与中位数相等的第一个数与最后一个数的位置 ④比较:(当前和中位数相等的数的个数)和(重数的... -
算法设计--众数和重数问题(分治法)
2016-10-19 21:36:13问题描述: 给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。...分治法解题过程主要分为分、治、合三个步骤“,应用该方法的基本过程如下: (1) 将原问题分解为若干个规模较小的子问题