題目三：
2.23如果一個數(shù)組A[1...n]中超過半數(shù)的元素都相同時尸曼，該數(shù)組被稱為含有一個主元素。給定一個數(shù)組萄焦，設計一個有效算法控轿，確定該數(shù)組中是否含有一個主元素冤竹。如果有，找出這個元素茬射。該數(shù)組的元素之間不一定存在順序鹦蠕，如整數(shù)之間就存在順序，可以作形如"A[i]>A[j]嗎"的比較與此不同的是在抛，該數(shù)組中的元素則不一定能做出這樣的比較钟病。（比如可以把數(shù)組中的元素設想成
GIF文件）但是，卻可以在常量時間內回答如下列形式的問題“A[i]>A[j]嗎”
（1）給出一個算法刚梭，以0(nlogn)時間完成本題
算法思想：
根據(jù)主元素的定義與題目要求肠阱，由于不能比較A[i]與A[j]大小，所以就不可以用排序的方式進行尋找主元素朴读，但是仍然可以比較元素之間相等與不相等屹徘，這里我采用刪除數(shù)組中兩個不相等的元素，主元素不變的思想衅金，尋找主元素噪伊。
代碼：
#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
