精华内容
下载资源
问答
  • 分治法求众数

    2018-01-04 21:14:47
    分治法求众数
  • 分治法求众数.doc

    2020-11-23 09:37:13
    算法设计与分析课内实验——分治法求众数。文档很齐全,包括算法分析过程和源代码(java语言eclipse环境)
  • 17088分治法求众数(优先做) 时间限制:1000MS 代码长度限制:10KB 提交次数:0 通过次数:0 题型: 编程题语言: G++;GCC;VC Description 给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数...

    17088 分治法求众数(优先做)

    时间限制:1000MS  代码长度限制:10KB
    提交次数:0 通过次数:0

    题型: 编程题   语言: G++;GCC;VC

     

    Description

    给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为
    众数。例如,S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。
    
    求众数方法很多,现要求你用分治算法来试一试,并分析其效率。
    
    编程任务:对于给定的由n个自然数组成的多重集S,采用分治算法编程计算S的众数及其重数。
    



     

    输入格式

    第1行多重集S中元素个数n;接下来的一行为集合S,有n个自然数。( n < 1000000 )
    


     

    输出格式

    结果输出:输出2个数,第1个数为众数,第2个为其重数。
    当有多个同样重数的众数,优先输出数值更小的数的众数。
    


     

     

    输入样例

    6 
    1 2 2 2 3 5


     

     

    输出样例

    2 3

     

    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include<algorithm>
    
    using namespace std;
    
    
    int main(){
        int n;
        scanf("%d", &n);
        int a[n];//a[n],用于输入
        int max,num;//最终输出的
        int tempmax,tempnum;//当前数字的最大数量和数字值
        for (int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        for (int i=0;i<n;i++)
        {
            if (i==0)
            {
                tempmax = max=1;
                tempnum = num=a[i];
                continue;
            }
            if(a[i]==a[i-1])//如果相等
            {
                tempmax++;
            }
            else//如果已经发生了改变,就和真正最大的比较一下
            {
                if(tempmax>max)//这个数的最多值比之前最多值还多
                {
                    max = tempmax;
                    num = tempnum;
                    tempnum=a[i];
                    tempmax=1;
                }
                else
                {
                    tempnum=a[i];
                    tempmax=1;
                }
            }
        }
        printf("%d %d",num,max);
        return 0;
    }
    

     

    展开全文
  • 分治法求众数问题 (配图)

    千次阅读 2017-07-13 19:01:00
    分治法求众数问题 (配图) 採用分治法。以中间为界限。 先计算环绕中间这个数字的众数情况。然后左右分开递归计算结果,取最值就可以。 左右递归计算的时候要先做推断。假如左边或是右边的个数都比已的重数...

    分治法求众数问题 (配图)


    採用分治法。以中间为界限。 先计算环绕中间这个数字的众数情况。然后左右分开递归计算结果,取最值就可以。

    左右递归计算的时候要先做推断。假如左边或是右边的个数都比已求的重数小。就不是必需计算了。即使左边或是右边所有都是一样的。那么他的重数也是小于已求的,所以不是必需进行运算,这一周在加深分治算法的学习,这题着实花了我不少时间。


    详细代码:


    // 用分治法求众数
    
    #include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    // 本程序的关键。 以中间的数字为界限。 确定左右起始和终止界限
    void split(int s[], int n, int &l, int &r)
    {
        int mid = n/2;
        for(l=0; l<n; ++l)
        {
            if (s[l] == s[mid])
                break;
        }
        for(r=l+1; r<n; ++r)
        {
            if (s[r] != s[mid])
                break;
        }
    
    }
    
    // num 众数。 maxCnt 重数
    void getMaxCnt(int &mid, int &maxCnt, int s[], int n)
    {
        int l, r;
        split(s, n, l, r);  // 进行分割。这个函数是本程序的关键
        int num = n/2;
        int cnt = r-l;
    
        // update
        if (cnt > maxCnt)
        {
            maxCnt = cnt;
            mid = s[num];
        }
    
        // l 表示左边的个数。左边的个数必须大于 maxCnt 才有必要搜寻
        if (l+1 > maxCnt)
        {
            getMaxCnt(mid, maxCnt, s, l+1);
        }
    
        // 右边搜寻, 右边数组的起始地址要变更
        if (n-r > maxCnt)
        {
            getMaxCnt(mid, maxCnt, s+r, n-r);
        }
    }
    
    int main(void)
    {
        int s[] = {1, 2, 2, 2, 3, 3, 5, 6, 6, 6, 6};
        int n = sizeof(s)/sizeof(s[0]);
    
        int maxCnt = 0;
        int num = 0;
        getMaxCnt(num, maxCnt, s, n);
        printf("%d %d\n", num, maxCnt);
    
        return 0;
    }
    



    大概思路图:






    展开全文
  • 分治法求众数问题

    千次阅读 多人点赞 2019-03-26 21:51:37
    读完问题我们发现起始求众数就是一个数组里面出现最多的数及其出现的次数,那么我们与其从左往右依次寻找还不如直接从中间往左右寻找更轻松,假设我们先出中位数的重数,如果发现左边的数的个数小于这个重数那么...

    问题描述:给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。要求对给定的又n个自然数的组成的多重集S,计算S的众数及其重数。

    读完问题我们发现求众数就是求一个数组里面出现最多的数,假设我们先求出中位数的重数,再求出中位数第一次出现的位置(中位数可能有多个),如果发现这个位置左边的数的个数小于这个重数那么我们就不用再往左边寻找了,因为左边已经没有比这个中位数的重数更大的数了,右边同理。

    经过上面的分析我们再把问题细化一下,找出这个中位数在这个数组中第一次出现的位置,取出从这个位置再加这个中位数的重数组成一个子数组,那么如果这个子数组左边的数目小于这个子数组的个数,也就是重数个数,那么左边不会有众数出现,右边同理。

    接下来就是代码了:

    #include <stdio.h>
    
    #define MAXSIZE 10
    
    int n = 0 ; //存储众数
    int s = 0 ; //存储众数的重数
    
    int count(int a[], int p, int q){
    /*统计中位数的重数*/
        int m = a[(p+q)/2] ;
        int counts = 0 ;
        for(int i=0; i<MAXSIZE; i++){
            if(a[i]==m)
                counts++ ;
        }
        return counts ;
    }
    
    int start(int a[], int p, int q){    
    /*求中位数第一次出现的位置*/
        int m = (p+q)/2 ;
        for(int i=p; i<q; i++){
            if(a[i]==a[m])
                return i;
        }
        return 0;
    }
    
    void find(int a[], int p, int q){
        int m = (p+q)/2 ;
        int ms = count(a, p, q) ;
        int left = start(a, p, q) ;
        if(ms > s){        //如果当前中位数的重数大于众数的重数,则代替众数
            s = ms ;       
            n = a[m] ;
        }
        if(q+1-(left+ms) > s){          //如果右边“空余”位置大于重数,往右边递归
    		find(a, left+ms, q) ;
    	}
            
        if(left > s){                 //如果左边“空余”位置大于重数,望左边递归        
            find(a, p, left) ;
        }
    }
    
    int main()
    {
    	int m, i;
    	int a[MAXSIZE];
    	
    	for(i=0; i<MAXSIZE; i++){
    		scanf("%d", &a[i]);
    	}
    
    	for(i=0; i<MAXSIZE; i++){
    		printf("%d ", a[i]);
    	}
    	printf("\n"); 
    
    	find(a, 0, MAXSIZE-1);
    
    	printf("众数:%d  它的重数:%d", n, s);
    
    	return 0;
    }

    本来觉得这样就好了,但看了评论,再看了代码,越想越觉得不太对劲,如果前面的数的个数虽然没有中位数重数多,但加上后面的数也许就比中位数重数大了,于是运行了下面的程序。。。

    果然有问题,说明这个程序思想还是有问题,我觉得应该排一下序再进行找众数的操作,于是我加了一个sort函数:

    void sort(int a[]){
    	int i, j;
    	for(i=0; i<MAXSIZE; i++){
    		for(j=0; j<MAXSIZE-i-1; j++){
    			if(a[j] > a[j+1]){
    				int t = a[j];
    				a[j] = a[j+1];
    				a[j+1] = t;
    			}
    		}
    	}
    }
    
    int main()
    {
    	int m, i;
    	int a[MAXSIZE];
    	
    	for(i=0; i<MAXSIZE; i++){
    		scanf("%d", &a[i]);
    	}
    	sort(a);
    
    	for(i=0; i<MAXSIZE; i++){
    		printf("%d ", a[i]);
    	}
    	printf("\n"); 
    
    	find(a, 0, MAXSIZE-1);
    
    	printf("众数:%d  它的重数:%d", n, s);
    
    	return 0;
    }

    再运行:

    好了,但是这样时间空间复杂度又都上升了,此时因为数组已经排序过了,那么

    C渣渣……老哥说的将10改成q也是没有问题的(将0改成p):

    int count(int a[], int p, int q){
    /*统计中位数的重数*/
        int m = a[(p+q)/2] ;
        int counts = 0 ;
        for(int i=p; i<q; i++){
            if(a[i]==m)
                counts++ ;
        }
        return counts ;
    }

    没有绝对好的算法,只有更好的算法。感谢建议以及提问。

    有问题call me,随叫随到    -_-

    展开全文
  • // 用分治法求众数 //参考:http://blog.csdn.net/core__code/article/details/47385045 #include <iostream> #include <cstdio> using namespace std; void split(int s[], int n, int &...
    // 用分治法求众数
    
    
    //参考:http://blog.csdn.net/core__code/article/details/47385045
    #include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    void split(int s[], int n, int &l, int &r)  //here should have a low limit, because the split for the top half will don't need to travel the whole array;
    {
        int middle = n / 2;
        for(l=0; l<n; l++)
        {
            if(s[l]==s[middle])
            {
                break;
            }
        }
    
        for(r=middle+1; r<n; r++)
        {
            if(s[r]!=s[middle])
            {
                break;
            }
        }
        return;
    }
    
    void getMaxCount(int s[], int n, int &maxCount, int &targetValue)  //high is not the upper of array, but the contain of array;
    {
        int l, r;   //l is the left edge of middle elements, r is right
        split(s, n, l, r);
        int middle = n / 2;
        if(r-l>maxCount)
        {
            maxCount = r - l;
            targetValue = s[middle];
        }
        if(maxCount<l)  //if the number on the left is less than the number of already getting the number of maxcount, the recurrence will not need to continue
        {
            getMaxCount(s, l, maxCount, targetValue);  //l is impossible to arrive
        }
        if(maxCount<n-r)
        {
            getMaxCount(s+r, n-r, maxCount, targetValue);
        }
        return;
    }
    
    int main(void)
    {
        int s[] = {1, 2, 2, 2, 3, 3, 3, 3, 3, 5, 6, 6, 6, 6, 6, 6};
        int n = sizeof(s)/sizeof(s[0]);
        int maxCount = 0;
        int targetValue = 0;    //this is meaningless, because the maxCount is zero, the showing times of every num is bigger than one
        getMaxCount(s, n, maxCount, targetValue);
        cout << targetValue << " " << maxCount;
        return 0;
    }

     

    转载于:https://www.cnblogs.com/1915884031A-qqcom/p/7595782.html

    展开全文
  • LeetCode 169分治法和其他几种简单解法 题意 给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在众数。 样例 示例 1: ...
  • (可以列出所有众数) 代码: #include&amp;amp;lt;iostream&amp;amp;gt; #include&amp;amp;lt;algorithm&amp;amp;gt; #include&amp;amp;lt;vector&amp;amp;gt; using namespace std...
  • 一组数据中,出现次数最多的数就叫这组数据的众数。 如果有两个或两个以上个数出现次数都是最多的,那么这几个数都是这组数据的众数。 如果所有数据出现的次数都一样,那么这组数据没有众数。 例1:1,2,3,3,4的...
  • 分治法——众数问题

    千次阅读 2020-01-10 20:04:47
    分治法——众数问题 给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。 多重集S中的最大元素称为众数。 文件输入: 第一行:多重集合S的个数 接下来的每一行输入S集合中的值 输出: 第一行...
  • 分治算法求众数

    千次阅读 2019-09-30 10:37:12
    多重集S中重数最大的元素称为众数。例如,S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。对于给定的n个自然数组成的多重集S,计算S的众数及其重数。 二.算法分析: 首先请求两个全局变量,用来存放不同数字的重...
  • 分治法求众数

    2019-11-19 20:15:58
    分治法求解众数问题,返回众数及其重数 url:https://www.cnblogs.com/yangykaifa/p/7162192.html https://www.cnblogs.com/pprp/p/9688481.html 每次查中间数出现的次数 */ #include<iostream> #include<...
  • 使用分治法解决众数问题

    热门讨论 2011-11-05 19:37:37
    这个程序使用分治法算法思想,求得一组数中的众数众数的重数。
  • c++分治法求解众数问题

    热门讨论 2009-11-02 10:18:53
    对随机生成的由n个自然数组成的多重集合S,应用分治法编程计算S的众数及其重数。
  • 分治法实现众数问题

    千次阅读 2016-10-23 22:42:03
    众数问题(分治法) 问题描述:给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数,多重集合S中重数最大的元素称为众数。例如,S={1, 2 ,2 ,2 ,3 ,5}。多重集合S的众数是2,其重数为3。算法...
  • 本人编写的数组下表、分支求解众数,包含源程序,实验报告。时间复杂度适中,比较适合算法分析!
  • 该资源是关于算法设计的,是文档,但是有附加了代码。
  • 分治法-众数问题java实现

    千次阅读 2018-09-15 09:42:21
    来填坑了,众数问题的分治法java实现。 首先说一下其他的思路 1.暴力法:选取其中的每个数遍历,得到每个数的重复次数,进行比较,O(n2) 2.先进行排序,O(nlgn),再去找,O(n) 3.使用额外空间(数组或者是哈希...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 612
精华内容 244
关键字:

分治法求众数