分治法求眾數

Problem Description

給定含有n個元素的多重集合S，每個元素在S中出現的次數稱為該元素的重數，多重集S中重數最大的元素稱為
眾數，例如，S={1，2，2，2，3，5}，多重集S的眾數是2，其重數為3，

求眾數方法很多，現要求你用分治演算法來試一試，并分析其效率，

編程任務：對于給定的由n個自然陣列成的多重集S，采用分治演算法編程計算S的眾數及其重數，

Input

第1行多重集S中元素個數n；接下來的一行為集合S，有n個自然數，( n < 1000000 )

Output

結果輸出：輸出2個數，第1個數為眾數，第2個為其重數，
當有多個同樣重數的眾數，優先輸出數值更小的數的眾數，

Sample Input

6 
1 2 2 2 3 5

Sample Output

2 3

Hint

提示陸續寫上來，不著急，先自行思考和討論……

Solution

題目說要用分治的解法，不過如果想過這題，一個for回圈也是暴力統計求解，

但既然是要學演算法，那我們當然要用分治的思想啦！

在這里插入圖片描述

分治策略

1.我們首先假設中間的元素是眾數
2. 然后由兩邊向中間遍歷，直到左右都出現值等于眾數的數，記錄下眾數和重數
3. 這樣就將一個陣列分為三部分，我們再對左右部分執行上述步驟
4. 注意：使用分治策略解決眾數問題需要原集合有序，在原集合無序的情況下需要對其排序，建議資料輸入之后先進行排序

當真正理解了分治的思想，這題就迎刃而解啦，這題的分治體現在將陣列分為三部分進行眾數的統計，可以參考下圖理解，

在這里插入圖片描述

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>



using namespace std;
typedef long long ll;
typedef pair<int,int>pi;

const int maxn=1e5+100;
const int N=1e6+100;
const int M=1e5+100;
const int mod=1e9+7;

int n,m,T;
int a[N];
int ans=0; //眾數的重數
int idx=0; //眾數的下標


void split(int l,int r) //分治演算法
{
    if(l>r)return;

    int ll=l; //記錄原來的l位置
    int rr=r; //記錄原來的r位置

    int mid=(l+r)>>1;

    for(; l<mid&&a[l]!=a[mid]; l++); //尋找眾數的最左邊

    for(; r>mid&&a[r]!=a[mid]; r--); //尋找眾數的最右邊
    
    //經過兩個for回圈后，眾數個數就是r-l+1

    if(ans<=r-l+1) //更新答案
    {
        if(ans==r-l+1)
        {
            idx=min(mid,idx);
        }
        else
            idx=mid;
        ans=r-l+1;
    }

    if(l-1-ll+1>=ans) //剪枝
        split(ll,l-1); // 對左邊部分分治

    if(rr-r-1+1>=ans) //剪枝
        split(r+1,rr); // 對右邊部分分治

}



void solve()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d",a+i);

    sort(a,a+n); //先排序，方便統計眾數個數

    int l=0;
    int r=n-1;

    split(l,r);

    printf("%d %d\n",a[idx],ans);

}


int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    solve();

    /*
    *
    *　　┏┓　　　┏┓+ +
    *　┏┛┻━━━┛┻┓ + +
    *　┃　　　　　　　┃
    *　┃　　　━　　　┃ ++ + + +
    *  ████━████+
    *  ◥██◤　◥██◤ +
    *　┃　　　┻　　　┃
    *　┃　　　　　　　┃ + +
    *　┗━┓　　　┏━┛
    *　　　┃　　　┃ + + + +Code is far away from 　
    *　　　┃　　　┃ + bug with the animal protecting
    *　　　┃　 　 ┗━━━┓ 神獸保佑,代碼無bug　
    *　　　┃ 　　　　　　 ┣┓
    *　　  ┃ 　　　　　 　┏┛
    *　    ┗┓┓┏━┳┓┏┛ + + + +
    *　　　　┃┫┫　┃┫┫
    *　　　　┗┻┛　┗┻┛+ + + +
    */
}

最后感謝小伙伴們的學習噢~

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/208086.html

標籤：其他

上一篇：C#/利用WPF視窗程式設計簡單計算器

下一篇：二極管作業原理及應用