已知一个整数序列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。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C、C++ 或 Java 语言描述算法，关键之处给出注释。

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

顺序表

1）给出算法的基本设计思想：算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素 Num。然后重新计数，确认 Num 是否为主元素。算法可分为以下两步：① 选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数 Num 保存到 c 中，记录 Num 的出现次数为 1；若遇到的下一个整数仍等于 Num，则计数加 1，否则计数减 1；当计数减到 0 时，将遇到的下一个整数保存到 c 中，计数重新记为 1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。② 判断 c 中元素是否是真正的主元素：再次扫描该数组，统计 c 中元素出现的次数，若大于 2，则为主元素；否则，序列中不存在主元素。

2）算法实现

int majority(int a[], int n) {
  if (n == 0) {
    return -1;
  }
  // 选取候选元素
  int num = a[0];
  int cnt = 1;

  // 如果主元素存在，会被以下过程筛选出来
  // 但是筛选出来的不一定是主元素
  for (int i = 1; i < n; i++) {
    if (a[i] == num) {
      // 候选元素个数 +1
      cnt++;
    } else {
      // 重新设置候选元素
      cnt--;
      if (cnt == 0) {
        num = a[i];
        cnt = 1;
      }
    }
  }

  // 再判断候选元素是不是主元素
  int m = 0;
  for (int i = 0; i < n; i++) {
    // 统计候选元素出现的次数
    if (a[i] == num) {
      m++;
    }
  }
  if (m > n / 2) {
    return num;
  }
  return -1;
}

【评分说明】① 若考生设计的算法满足题目的功能要求且正确，则 (1)、(2) 根据所实现算法的效率给分，细则见下表：

② 若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照①的标准给分。③ 若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。

(3) 说明算法复杂性：参考答案中实现的程序的时间复杂度为O(m)，空间复杂度为O(1)。【评分说明】若考生所估计的时间复杂度与空间复杂度与考生所实现的算法一致，可各给 1 分。【说明】本题如果采用先排好序再统计的方法，只要解答正确，最高可拿 9 分，因此对于统考算法题，去花费大量时间去思考最优解法是得不偿失的。