博客

问题描述：

给定含有 n 个元素的多重集合 S，每个元素在 S 中出现的次数称为该元素的重数。多重集合 S 中重数最大的素称为众数。例如多重集合 S={1,2,2,7,2,7,5}，其中众数是 2，其重数为 3。用分治法设计并实现在多重集合中找众数及其重数的算法，要求算法的时间复杂性在坏情况下不超过 O(nlogn)。

方法一：穷举

对数组中的每一个数计算其个数，最终最终选出最大的。时间复杂度为O（n^2）。代码就不贴了，两重循环可以实现。

方法二：分治法


选出第一个数作为基准，用两个指针遍历剩下元素，先从右向左，遇到比基准小的或遇到左指针就停下；再从左向右，遇到比基准大的或遇到右指针就停下。



然后交换左右指针的值。当左右指针相遇时结束循环，并且将基准与其交换位置。显然，我们可以在遍历时顺便统计出基准在此段数组中元素个数。



因此，遍历结束后计算出基准左边和右边剩下的元素个数。如果左边或右边的元素个数比统计得到基准个数多的话，则以左边或右边的数据段为参数（因为剩下数据元素小于基准个数时，则不可能出现众数），递归进行以上操作。递归边界条件为数据段中元素剩下一个或没有。


由于以上操作和快速排序基本相同，而快速排序的平均时间复杂度为O（nlogn）。所以我推测（仅仅是推测…不能给出证明…）算法的平均时间复杂度也是为O（nlogn）。并且很可能还要在nlogn的基础上减去某个常数或变量，因为当左右数据段所剩元素个数小于基准个数时停止递归。（望有大神来告诉我这种想法有没有根据）

最坏情况为O（n^2）.因为在选基准时无法保证每次都能选出让数据段平均分割的基准，所以无法在最坏情况下达到O（nlogn）。

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#define MAXLEN 50
using namespace std;

typedef struct ITEM_Sets
{
    int element[MAXLEN];
    int Size;
    int mode;
    int times;
}Sets;

void Swap(int &a,int &b)
{
    int t;
    t = a;
    a = b;
    b = t;
}

void divided(Sets &s,int keyIndex,int start,int rear)
{
    int cnt = 0;
    int keyNum = s.element[keyIndex];
    int left = start;
    int right = rear;
    int flag = 1;
    if(left >= right) return;///边界条件
    while(left < right){
        while(s.element[left] <= keyNum && left <= right){
            if(s.element[left] == keyNum) {
                cnt++;
            }
            left++;
        }

        while(s.element[right] >= keyNum && left < right){
            if(s.element[right] == keyNum){
                cnt++;
            }
            right--;
        }
        if(left < right){
            Swap(s.element[left],s.element[right]);
        }
    }
    if(left > right) left--;
    if(s.element[keyIndex] <= s.element[left]){
        Swap(s.element[keyIndex],s.element[left-1]);
        flag = 1;
    }
    else{
        Swap(s.element[keyIndex],s.element[left]);
        flag = 0;
    }

    if(cnt>s.times){
        s.times = cnt;
        s.mode = keyNum;
    }

    if(rear-right>= cnt){
        divided(s,right,right,rear);
    }
    if(left-start>= cnt){
        if(flag == 1){
            divided(s,start,start,left-2);
        }
        else if(flag == 0){
            divided(s,start,start,left-1);
        }
    }
}

int main(){
    Sets s;
    srand(time(NULL));
    int n;
    while(cin>>n){///输入要生成随机数的个数
        if(n==0)break;
        s.Size = n;
        s.mode = -1;
        s.times = 0;
        if(n>MAXLEN) continue;
        for(int i=0;i<n;i++){
            s.element[i] = rand()%10+1;
        }///生成一组随机数
        for(int i=0;i<n;i++){
            cout<<s.element[i]<<" ";
        }
        cout<<endl;
        divided(s,0,0,n-1);
        cout<<"Mode:"<<s.mode<<" Times:"<<s.times<<endl;
        cout<<endl<<endl;
        system("pause");
        system("cls");
    }
    return 0;
}

方法三：分治法加预处理

以上两种方法都没能在最坏情况下达到O（nlogn）的时间复杂度。但方法二已经非常接近了，它未能达到要求的原因在于选出的基准不能保证分割时恰好分成两等分。所以我们需要一些预处理让选出的基准为当前数据段的中间数。显然，我们需要先排序。

要时间复杂度为O（nlogn），则预处理的时间复杂度不能超过O（nlogn）。所以我们需要用到归并排序，因为归并排序最坏情况下不会超过O（nlogn）。剩下的事情就非常简单了，

每次选择时选出数据段的中间的数据作为基准，然后从中间向两边扩展着计算基准个数，遇到不是基准的元素时停下

。再计算出剩下左右两边的数据段的元素个数，多于基准个数的则递归进行以上操作（剩下的不可再排序）。

显然，排序和求解众数的算法时间复杂度都为O（nlogn），并列的O（nlogn）仍为O（nlogn）。

以下代码应该用归并排序的，但我当初写的时候用了快速排序。

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#define MAXSIZE 1000
using namespace std;

typedef struct ARRAY
{
    int a[MAXSIZE];
    int mode;
    int times;
    int len;
}Array;

void initialArray(int len,Array &arr)
{
    arr.len = len;
    arr.mode = -1;
    arr.times = 0;
    for(int i=0;i<len;i++){
        arr.a[i] = rand()%15 + 1;
    }
}

void displayArray(Array arr)
{
    for(int i=0;i<arr.len;i++){
        cout<<arr.a[i]<<" ";
    }
    cout<<endl;
}

void swapNum(int &i,int &j)
{
    int t;
    t = i;
    i = j;
    j = t;
}

void check(int a[],int l,int r)
{
    for(int i=l;i<=r;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

void quickDivide(Array &arr,int l,int r)
{
    if(l >= r) return;
    int i = l;
    int j = r;
    int pivot = arr.a[l];
    while(i < j){
        while(i < j && arr.a[j] >= pivot){j--;}
        while(i < j && arr.a[i] <= pivot){i++;}
        if(i < j){
            swapNum(arr.a[i],arr.a[j]);
        }
    }
    swapNum(arr.a[l],arr.a[i]);
    quickDivide(arr,l,i-1);
    quickDivide(arr,i+1,r);
}

void quickSort(Array &arr)
{
    quickDivide(arr,0,arr.len-1);
}

void findMode(Array &arr,int l,int r)
{
    if(l >= r) return;
    int mode = arr.a[(r-l)/2+l];
    int i = (r-l)/2-1+l;
    int j = (r-l)/2+1+l;
    int times = 1;
    while(arr.a[i] == mode || arr.a[j] == mode){
        while(i >= l && arr.a[i] == mode){
            i--;
            times++;
        }
        while(j <= r && arr.a[j] == mode){
            j++;
            times++;
        }
    }
    if(times > arr.times) {
        arr.times = times;
        arr.mode = mode;
    }
    if(i-l >= times){
        findMode(arr,l,i);
    }
    if(r-j >= times){
        findMode(arr,j,r);
    }
}

int main()
{
    Array arr;
    int len;
    srand(time(NULL));
    while(cin>>len){///输入随机数组长度
        if(len <= 0) break;
        initialArray(len,arr);///生成随一组机数
        quickSort(arr);///应该写归并排序的，但我当初写了快速排序
        displayArray(arr);
        findMode(arr,0,arr.len-1);///求解众数，重数
        cout<<arr.mode<<" "<<arr.times<<endl;
    }
    return 0;
}