算法準備-分治算法解決衆數求解問題

分治算法解決衆數求解

一般來講分治算法需要處理的序列是有序的，是以該算法處理衆數問題的時候也需要進行排序

分治算法适合于解決可以将問題規模減小的問題，直到這個小問題可以直接解決

這裡還是需要想一下這個過程，如何用分治算法進行求解

不可能将所有子問題分解為單個數值的求解，但是我們可以做到的是将某一個出現很多次的數字進行統計

這也就是本體解決思路了，下面舉一個例子（已經排序好的）：

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;
}
           

代碼改變世界