首页 > 编程语言 > 详细

算法准备-分治算法解决众数求解问题

时间:2018-09-21 22:31:39      阅读:60      评论:0      收藏:0      [点我收藏+]

标签:查询   更新   所有   main   解决   就是   记录   urn   有一个   

分治算法解决众数求解

一般来讲分治算法需要处理的序列是有序的,所以该算法处理众数问题的时候也需要进行排序

分治算法适合于解决可以将问题规模减小的问题,直到这个小问题可以直接解决

这里还是需要想一下这个过程,如何用分治算法进行求解

不可能将所有子问题分解为单个数值的求解,但是我们可以做到的是将某一个出现很多次的数字进行统计

这也就是本体解决思路了,下面举一个例子(已经排序好的):

1 2 2 3 3 3 4 5 6
0 1 2 3 4 5 6 7 8

经过排序以后,打算进行中间位置的数的求解,也就是先数3的个数(记录左右边界3,5)

然后在左边界的左边进行递归求解,在右边界的右边进行递归求解

在这个过程中有一个优化,如果左侧的数已经不足以大于当前的最大重数,那就没必要在进行统计左侧内容,右侧同理。

下面是代码

#include <bits/stdc++.h>

using namespace std;

//找到从左,从右开始的跟a[mid]一样的数
//得到左右边界为low,high
void solve(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;
        }
    }
}

void _MaxCnt(int &mid, int &maxCnt, int a[],int n)
{
    int l, r;
    solve(a,n,l,r);
    int num = n/2;
    int cnt = r-l;

    //如果众数为当前,那就更新
    if(cnt > maxCnt){
        maxCnt = cnt;
        mid = a[num];
    }
    //左侧进行递归查询
    if(l+1 > maxCnt){
        _MaxCnt(mid,maxCnt,a,l+1);
    }
    //右侧进行递归查询
    if(n-r > maxCnt){
        _MaxCnt(mid,maxCnt,a+r,n-r);
    }
}

int main(){
    int a[] = {1,2,3,3,3,4,9,6,7,7,7,7,9,5,10,10,12,
              12,14,14,15,14,31,23,5,23,4,43,3,2,3,4
              ,3,2,1,1,34,2,3,2,2,2,22,0,2,12,5,5,5,
              5,5,5,5,6,5};
    int n = sizeof(a)/sizeof(a[0]);
    sort(a,a+n);

    int maxCnt = 0;
    int num = 0;

    _MaxCnt(num,maxCnt,a,n);

    cout << num << " " << maxCnt << endl;

    return 0;
}

算法准备-分治算法解决众数求解问题

标签:查询   更新   所有   main   解决   就是   记录   urn   有一个   

原文:https://www.cnblogs.com/pprp/p/9688481.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号