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

    2021-04-08 19:42:07
    C语言 众数问题 分治法 解题思路: ①排序:拿到一个乱序的数列,先排序(顺序跳过这一步) ②找中位数 ③ 遍历:得到与中位数相等的第一个数与最后一个数的位置 ④比较:(当前和中位数相等的数的个数)和(重数的...

    C语言 众数问题 分治法

    解题思路:
    ①排序:拿到一个乱序的数列,先排序(顺序跳过这一步)
    ②找中位数
    ③ 遍历:得到与中位数相等的第一个数与最后一个数的位置
    ④比较:(当前和中位数相等的数的个数)和(重数的大小)大于——>更新众数与重数
    ⑤分治:
    左边非中位数的个数>一坨中位数的个数 ——>众数有可能在左边
    右边非中位数的个数<一坨中位数的个数 ——>众数有可能在右边

    代码实现:

    #include <stdio.h>
    #include <stdlib.h>
    #define MAX 20
    int mode = 0;//众数
    int multiplicity  = 0;//重数
    
    void FindMode(int n[],int low, int high)
    {
        //找到中位数
        int mid = n[(low+high)/2];
    
        //与中位数相等的第一个数与最后一个数的位置
        int first = 0,last =  0;
        for(int i=low;i<high;i++)
        {
            if(n[i] == mid)
            {
                first = i;
                break;
            }
        }
        for(int i = first;i<high;i++)
        {
            if(n[i] != mid)
            {
                last = i;
                break;
            }
        }
    
        if(multiplicity<last-first+1)
        {
            multiplicity = last-first+1;
            mode = mid;
        }
    
        if(first+1>last-first+1)
        {
            FindMode(n,low,first);
        }
    
        if(high-last+1>last-first+1)
        {
            FindMode(n,last,high);
        }
    }
    
    void QuickSort(int *arr, int low, int high)
    {
        if (low < high)
        {
            int i = low;
            int j = high;
            int k = arr[low];
            while (i < j)
            {
                while(i < j && arr[j] >= k)     // 从右向左找第一个小于k的数
                {
                    j--;
                }
    
                if(i < j)
                {
                    arr[i++] = arr[j];
                }
    
                while(i < j && arr[i] < k)      // 从左向右找第一个大于等于k的数
                {
                    i++;
                }
    
                if(i < j)
                {
                    arr[j--] = arr[i];
                }
            }
    
            arr[i] = k;
    
            // 递归调用
            QuickSort(arr, low, i - 1);     // 排序k左边
            QuickSort(arr, i + 1, high);    // 排序k右边
        }
    }
    
    int main()
    {
        int a[MAX];
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
    
        //快速排序
        QuickSort(a, 0, n-1);
        for(int i=0;i<n;i++)
        {
            printf("%d ",a[i]);
        }
        printf("\n");
    
        FindMode(a, 0, n-1);
        printf("众数为:%d",mode);
        return 0;
    }
    

    疑惑:如果有多个众数怎么办?

    (有问题烦请批评指证)

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

    千次阅读 2020-12-21 13:58:10
    多重集S中重数最大的元素称为众数。例如,S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。对于给定的由n 个自然数组成的多重集S,计算S的众数及其重数。如果出现多个众数,请输出最小的那个。 Input 输入数据...
    • 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 <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;
    }
    
    • 运行结果

    在这里插入图片描述

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

    千次阅读 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 KiB

    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
    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;
    }
    
    
    展开全文
  • 众数问题分治法解决)

    千次阅读 2019-09-26 10:14:04
    一:题目 给定含有n个元素的多重集合s,每个元素在s中出现的次数称为该元素的重数...仔细思考,这道题目还可以用分治法来解决。 解决步骤: ①给数组排序; ②找出中位数v并且确定中位数的个数num和左右边界; ...

    一:题目


    给定含有n个元素的多重集合s,每个元素在s中出现的次数称为该元素的重数,多重集s中重数最大的元素称为众数,给定多重集合s,求s中的众数集重数。

    二:思路


    首先,我们最容易想到的就是统计每个数的出现次数,然后比较得出结果。这个思路可以利用容器来实现。

    仔细思考,这道题目还可以用分治法来解决。

    解决步骤:

    ①给数组排序;

    ②找出中位数v并且确定中位数的个数num和左右边界;

    ③如果左边界左边数字的个数比num大,说明众数可能在左边,重复②之后的步骤;

    ④如果右边界右边数字的个数比num大,说明众数可能在右边,重复②之后的步骤;

    ⑤得出众数v和重数num。

    三:代码


    public class solution {
        public static final int maxn = 10000;
        public static int[] a = new int[maxn];
        public static int num, v;
    
        public static void main(String[] args) {
            Scanner cin = new Scanner(new BufferedInputStream(System.in));
            System.out.println("请输入数组长度(<=10000):");
            int n = cin.nextInt();
            Random rand = new Random();
            for (int i = 0; i < n; i++) {
                a[i] = (rand.nextInt(100) + 1) % 20;
            }
            Arrays.sort(a, 0, n);
            for(int i = 0; i < n; i++) {
                System.out.println(a[i]);
            }
            solve(0, n - 1);
            System.out.println("Value:" + v);
            System.out.println("Number:" + num);
        }
    
        public static void solve(int l, int r) {
            if (l > r)
                return;
            int mid = (l + r) / 2;
            int i = mid, j = mid;
            while (i >= 0 && a[i] == a[mid])
                i--;
            while (a[j] == a[mid] && j <= a.length - 1)
                j++;
            if (j - i - 1 > num) {
                num = j - i - 1;
                v = a[mid];
            }
            if (i - l + 1 > num) {
                solve(l, i);
            }
            if (r - j + 1 > num) {
                solve(j, r);
            }
        }
    }

     

    展开全文
  • 问题描述:给定含有n个元素的多重集合S,每个元素在S中出现的...算法设计:对于给定的由n个自然数组成的多重集S,计算S的众数及其重数。S有序。 #include <iostream> using namespace std; int larg...
  • 使用分治法解决众数问题

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

    万次阅读 多人点赞 2016-10-30 13:12:56
    一、问题描述 给定含有n个元素的多重集合s,每个元素在s中出现的次数称为该元素的重数,多重集s中重数最大 的元素称为众数,给定多重集合s,求s中的众数集重数。 二、算法思想及描述 我在网上看了,感觉都晦涩难懂,...
  • 分治法求解众数问题,里头用到了快速排序算法
  • 1.问题描述: 给定含有 n 个元素的多重集合 S,每个元素在 S 中出现的次数称为该元素的重数,多重 集合 S 中重数最大的元素称为众数。例如,S={1, 2 ,2 ,2 ,3 ,5}。多重集合 S 的众数是 2,其重数为 3。 2.算法设计...
  • 分治法实现众数问题

    千次阅读 2016-10-23 22:42:03
    众数问题分治法问题描述:给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数,多重集合S中重数最大的元素称为众数。例如,S={1, 2 ,2 ,2 ,3 ,5}。多重集合S的众数是2,其重数为3。算法...
  • 给定一个大小为n的数组,找到其中的众数众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2...
  • 记录一下第一次写CSDN,最近刚看了算法与数据结构的相关视频,其中看到了分治众数分治求幂的视频后对它们的时间复杂度的不同产生了强烈的探知欲,在看了一些博客后,根据知识和代码,算是明白了它们的不同。...
  • c++分治法求解众数问题

    热门讨论 2009-11-02 10:18:53
    对随机生成的由n个自然数组成的多重集合S,应用分治法编程计算S的众数及其重数。
  • A - 众数问题 Description 给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如,S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。对于给定的由n ...
  • 分治法——众数问题

    千次阅读 2020-01-10 20:04:47
    分治法——众数问题 给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。 多重集S中的最大元素称为众数。 文件输入: 第一行:多重集合S的个数 接下来的每一行输入S集合中的值 输出: 第一行...
  • 多重集s中重数最大的元素称为众数,如s = {1,2,2,2,5,3}。多重集s的众数是2,其重数为3。 分析: 先用快速排序给数组从小到大排好序,接着找出中位数,(元素个数除2就是它的位置),以中位数为参考点,找出中位数...
  • 分治法应用场景之一:大学选毕业生代表 【分】 提出【大范围问题 】 校长告诉大四级长:从所有大四学生中选出毕业生代表 处理为【小范围问题】大四级长告诉每个系主任:从各自的系里面选一个系学生代表 再...
  • 分治法众数问题

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

    2019-10-23 20:16:53
    多重集S中重数最大的元素称为众数。例如,S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。对于给定的由n 个自然数组成的多重集S,计算S的众数及其重数。如果出现多个众数,请输出最小的那个。 Input 输入...
  • LeetCode169求众数——分治

    千次阅读 2018-03-04 14:40:05
    题目:给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且数组中的众数永远存在。方法:Hash Table将每个数字仿佛哈希表中,记数,直到某个...
  • 算法实现题 2-2 众数问题 问题描述: 给定含有 n 个元素的多重集合 S,每个元素在 S 中出现的次数称为该元素的重数。多重 集 S 中重数最大的元素称为众数。 例如,S={1,2,2,2,3,5}。 多重集 S 的众数是 2,其重...
  • 众数问题 Description 给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如,S={1,2,2,2,3,5}。多重集S的众数是2,其重数为3。对于给定的由n 个...
  • 通过分治,每次求解s[mid]的出现次数,然后统计。将s拆分成两个部分,然后再分别求解。 代码: #include<iostream> #include<algorithm> #include<vector> using std::cin; using std::cout; ...
  • 题目描述:给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在众数。 哈希: 时间复杂度:O(n) 空间复杂度:O(n) class ...

空空如也

空空如也

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

众数问题分治法算法