题12

题12

题目

【2013 统考真题】已知一个整数序列 ，其中 。若存在 且 ，则称 为 的主元素。例如 ，则 为主元素；又如 ，则 中没有主元素。假设 中的 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出 的主元素。若存在主元素，则输出该元素；否则输出 。要求：

⑴ 给出算法的基本设计思想。

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

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

分析

题3

解

1. 算法的基本设计思想: 算法的策略是从前向后扫描数组元素, 标记出一个可能成为主元素的元素 Num。然后重新计数, 确认 Num 是否是主元素。

算法可分为以下两步:

① 选取候选的主元素。依次扫描所给数组中的每个整数, 将第一个遇到的整数 Num 保存到 c 中,记录 Num 的出现次数为 1 ; 若遇到的下一个整数仍等于 Num,则计数加 1,否则计数减 1 ; 当计数减到 0 时,将遇到的下一个整数保存到 c 中,计数重新记为 1,开始新一轮计数, 即从当前位置开始重复上述过程, 直到扫描完全部数组元素。

② 判断 c 中元素是否是真正的主元素。再次扫描该数组,统计 c 中元素出现的次数,若大于 n/2 ,则为主元素; 否则,序列中不存在主元素。

2. 算法实现如下:

int Majority(int A[], int n) {
    int i, c, count = 1; // c 用来保存候选主元素, count 用来计数
    c = A[0]; // 设置 A[0] 为候选主元素
 
    for (i = 1; i < n; i++) // 查找候选主元素
        if (A[i] == c)
            count++; // 对 A 中的候选主元素计数
        else
            if (count > 0) // 处理不是候选主元素的情况
                count--;
            else { // 更换候选主元素, 重新计数
                c = A[i];
                count = 1;
            }
 
    if (count > 0)
        for (i = 0, count = 0; i < n; i++) // 统计候选主元素的实际出现次数
            if (A[i] == c)
                count++;
 
    if (count > n / 2) return c; // 确认候选主元素
    else return -1; // 不存在主元素
}

3. 实现的程序的时间复杂度为 O(n) ,空间复杂度为 O(1) 。

说明: 本题若采用先排好序再统计的方法 [时间复杂度为 O(nlog2n) ],则只要解答正确,最高可拿 11 分。即便是写出 O(n^2) 的算法,最高也能拿 10 分,因此对于统考算法题,花费大量时间去思考最优解法是得不偿失的。