Responsive image

问题 D: 第4关:数组的主元素查询

问题 D: 第4关:数组的主元素查询

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 239
[提交][状态][讨论版][命题人:]

题目描述

已知一个整数序列A=(a0, a1,…an-1),其中0≤ai<n(0≤i<n)。若存在ap1=ap2…=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。
组合提交代码,仅支持C++
#include <iostream>

using namespace std;
int MainElement(int a[], int n) { //求整数序列a的主元素
  /**************begin************/
  


  /**************end************/
}
int main() {
  int n;
  while (cin >> n) {
    if (n == 0) break;
    int * a = new int[n];
    for (int i = 0; i < n; i++) //输入数据
    {
      cin >> a[i];
    }
    cout << MainElement(a, n) << endl; //输出主元素的值
  }
  return 0;
}



输入描述

多组数据,每组数据两行。第一行为一个整数n,代表数组中有n个元素。第二行为数组中的n个元素(元素之间用空格分隔)。当n等于0时,输入结束。

输出描述

每组数据输出一行,若数组中存在主元素,输出主元素的值,若数组中不存在主元素,则输出-1。

样例输入

8
0 5 5 3 5 7 5 5
9
0 5 5 3 5 1 5 7 0
0

样例输出

5
-1

提示


组合提交代码,你仅需要提交





int MainElement(int a[], int n) { //求整数序列a的主元素


  /**************begin************/


  










  /**************end************/


}




[提交][状态]
ACM算法攻关部