题目三：
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 100000
using 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
