2.23假如一个数组A[1…n]中超过半数的元素都相同时，该数组被称为含有一个主元素。 给定一个数组，设计一个有效算法，确定该数组中能否含有一个主元素。假如有，找出这个元素。 该数组的元素之…

题目三：

2.23假如一个数组A[1…n]中超过半数的元素都相同时，该数组被称为含有一个主元素。给定一个数组，设计一个有效算法，确定该数组中能否含有一个主元素。假如有，找出这个元素。该数组的元素之间不肯定存在顺序，如整数之间就存在顺序，可以作形如”A[i]>A[j]吗”的比较与此不同的是，该数组中的元素则不肯定能做出这样的比较。（比方可以把数组中的元素设想成
GIF文件）但是，却可以在常量时间内答复如下列形式的问题“A[i]>A[j]吗”
（1）给出一个算法，以0(nlogn)时间完成本题

算法思想：

根据主元素的定义与题目要求，因为不能比较A[i]与A[j]大小，所以就不可以用排序的方式进行寻觅主元素，但是依然可以比较元素之间相等与不相等，这里我采用删除数组中两个不相等的元素，主元素不变的思想，寻觅主元素。

代码：

#include<iostream>#include <vector>#define INFINITY 100000using namespace std;int GetMain(vector<int>&A){    int count = 0, mainE;    for (int i = 0; i < A.size(); i++)    {        if (count == 0)        {            mainE = A[i];            count = 1;        }        else        {            if (mainE == A[i])                count++;            else                count--;        }    }    if (count > 0)        return mainE;    else        return INFINITY;}int main(void){    vector<int>A;    int n;    cin >> n;    for (int i = 0; i < n; i++)    {        int temp;        cin >> temp;        A.push_back(temp);    }    int temp = GetMain(A);    if (temp != INFINITY)        cout << "主元素为：" << temp;    else        cout << "没有主元素";    system("pause");    return 0;}

测试案例：

image.png