题目

已知一个整数数列A={a0,a1,a2,…,an-1}，其中0<=ai<n(0<=i<n)。若存在ap1=ap2=ap3=…=apm=x且m>n/2(0<=pk<n,1<=k<=m)，则成x为A的主元素。例如A={0,5,5,3,5,7,5,5}，则5为主元素；又如A={0,5,5,3,5,1,5,7}，则A中没有主元素。假设A中的n个元素保存在一维数组中，请设计一个尽可能高效的算法，找出数组A的主元素。若存在主元素，则输出主元素；否则，输出-1。要求：

1. 给出算法的基本设计思想。
2. 根据设计思想，用C/C++实现算法。
3. 说明所设计的算法的时间复杂度和空间复杂度。

基本设计思想

思路一

1. 由题目可知，主要要求找出数组中重复值最多的元素并判断它是否为主元素。
2. 因此，我们可以考虑先利用二路归并排序算法将数组变为有序。
3. 接下来，再利用双指针i，j用于记录数组中相同值元素的个数，用变量count记录最大个数，变量mainElem记录主元素值。
4. 结束数组遍历后，将count值与数组长度/2相比。若大于数组长度/2，则返回mainElem；否则，返回-1。

思路二

1. 我们可以考虑计数排序的思想，利用一个辅助容器map记录arr中各元素值以及出现的个数。
2. 然后，找出辅助数组中值最大的元素并判断是否符合主元素要求。即可完成题目要求。

代码实现

只实现算法二的代码

int LinearList::Question_12()
{
    if(arr.length <= 1)
        return arr.data[0];

    map<int,int> mapp;      //设置map容器用于存储arr数组中的所有元素值和对应的元素个数
    mapp[arr.data[0]] = 1;

    for(int i = 1;i < arr.length;i ++)
    {
        int value = arr.data[i];
        if(mapp.count(value))
            mapp[value]++;
        else
            mapp[value] = 1;
    }

    int maxCount = -1,maxElem = 0;
    for(auto &pair : mapp)      //遍历map，找出重复次数最多的元素
    {
        if(pair.second >= maxCount)
        {
            maxElem = pair.first;
            maxCount = pair.second;
        }
    }

    if(maxCount > arr.length/2) //判断是否符合主元素条件
        return maxElem;
    else
        return -1;
}

效果