数据结构算法每日一练（六）数组主元素

难度： ⭐⭐⭐

题目：已知一个整数序列$A = (a_0，a_1……a_{n-1})$,其中 $0≤a_i<n(0≤i<n)$。

若存在$a_{pi}=a_{p2}= ……a_{pm}=x且m>n/2 (0≤p_k<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）算法思想：构建一个大小为n的数组，用于对每个整数的计数，遍历一遍序列然后再遍历1次这个数组找到最大值，然后判断条件是否符合主元素条件。此解法易思考。

（2）

/**
 * 主元素算法
 * @param A 判定数组
 * @param n 数量n
 * @return
 */
int Majority(int A[], int n) {
    int arr[n];
    int i, *B;
    B = (int *)malloc(sizeof(int)*n); //分配空间
    memset(B, 0, sizeof(int)*n); //赋初值为0
    for (int i = 0; i < n; i++) {
        B[ A[i] ]++; //将A数组对应的值在B数组对应+1；
    }
    int max = 0;
    for (int j = 0; j < n; j++) { //遍历完查最大数量的数值
        if (B[j] > max) {
            max = B[j];
        }
    }
    if (max > n / 2)  //判断最多数量的数是否满足主元素的条件大于n/2
        return max;
    else
        return -1;

}

（3）时间复杂度为$O(n)$，空间复杂度为$O(n)$;

解法二（最优解法）

（1）算法思想：策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确定Num是否是主元素。

算法可分为以下两步:

①选取候选的主元素。依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍

等于Num，则计数加1，否则计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重

复上述过程，直到扫描完全部数组元素。

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

（2）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 主元素算法
 * @param A 判定数组
 * @param n 数量n
 * @return
 */
int Majority1(int A[], int n) {
    int i , c, count = 1;
    c = A[0]; //设置A[0]为候选主元素
    for (int i = 1; i < n; i++) {
        if (A[i] == c) { //如果是候选主元素，则计数加一
            count++;
        }else {
            if (count > 0) { //如果不是候选主元素，计数减一
                count--;
            }else { //计数为0，更换候选主元素
                c = A[i];
                count = 1;
            }
        }
    }//for
    if (count > 0) { //统计候选主元素的次数
        for (int i = count = 0; i < n; i++) {
            if (A[i] == c) {
                count++;
            }
        }
    }//if
    if (count > n / 2)  //判断条件
        return c;
    else
        return -1;
}
（3）时间复杂度为$O(n)$，空间复杂度为$O(1)$

解法三

（1）算法思想：先对整个序列进行排序，然后遍历一遍看哪个元素最多，此算法也易想，相较于上述两种算法效率稍低。

（2）时间复杂度

若使用快速排序或者归并排序时间复杂度为$O(nlog_2n)$，冒泡排序获插入排序等时间复杂度为$O(n^2)$

快速排序空间复杂度为$O(log_2n)$，归并排序空间复杂度为$O(n)$