2013 年 408 数据结构 · 第 41 题

已知一个整数序列  $A=(a_0,a_1,\dots ,a_{n-1})$  ，其中  $0\le a_i<n$ $(0\le i<n)$  。

若存在  $a_{p_1}=a_{p_2}=\cdots =a_{p_m}=x$  且  $m>n/2$ $(0\le p_k<n,1\le k\le 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++ 或 Java 语言描述算法，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度和空间复杂度。