算法：空间换时间（计数排序思想）

求主元素：主元素为数组中出现超过n/2次的元素
核心代码： B[A[i]]++;

//我的作答:没有使用max，多使用了一次for循环。易于想到。
#include <iostream> 

using namespace std;

int Majority1(int A[],int n){
    int *B = new int[n];              //申请长度为n的辅助计数数组
    for(int i=0;i<n;i++)                
        B[i]=0;                       //计数数组元素初始化为0
    for(int i=0;i<n;i++)              //计数数组对应位置+1
        B[A[i]]++;                    
    for(int j=0;j<n;j++){             //遍历寻找并输出主元素
        if(B[j] > n/2){
            cout<<j<<endl;
            return j;
        }
        else
            continue;
    }
    cout<<-1<<endl;
    return -1;
}

int main()
{
    int A[]={0,5,5,3,5,7,5,5,6,6,6,6,6,6,6,6,6,6};
    Majority1(A,18);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

时间复杂度：O(n)，空间复杂度：O(n)

申请一维数组的写法见这里

//408统考13年41题官方次级答案
//最优解空间复杂度为O(1)，难于想到，这里不提供
#include <iostream> 

using namespace std;

int Majority1(int A[],int n){
    int i,*B,max=0;
    B = (int *)malloc(sizeof(int)*n); //申请长度为n的辅助计数数组
    for(i=0;i<n;i++)                
        B[i]=0;                       //计数数组元素初始化为0
    for(i=0;i<n;i++){
        B[A[i]]++;                    //计数数组对应位置+1
        if(B[A[i]]>B[max])            
            max=A[i];
    }
    if(B[max]>n/2){ 
        //cout <<max<<endl;
        return max;
    }
    else{
        //cout<<-1<<endl;
        return -1;
    }
}

int main()
{
    int A[]={0,5,5,3,5,7,5,5};
    Majority1(A,8);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32