博客

问题：（2013年408统考真题）

已知一个整数序列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、第一种方法（笨方法但直接）

算法思想：


构建一个大小为n的计数数组counter，用于对原数组s中每个整数的计数，遍历完整个原数组s后遍历数组counter，若counter中有数值大于n/2则输出这个整数，没有则输出-1。

时间复杂度为O(n),空间复杂度为O(n)

#include"head.h";
int main(){
	int n;
	printf("请输入数组长度:");
	scanf_s("%d", &n);
	int counter[100];//100是初始数组长度
	for (int i = 0; i < n; i++) {
		counter[i] = 0;//初始化计数数组
	}
	int s[100];
	printf("请输入数组元素:");
	for(int j=0;j<n;j++){
		scanf_s("%d",&s[j]);
		counter[s[j]]++;
	}
	int  p= 1;
	for(int i=0;i<n;i++){
		if (counter[i] > n / 2) {
			p = 0;
			printf("主元素为%d", i);
			break;
		}		
	}
	if (p)
		printf("-1\n");
	return 0;
}

2、第二种方法（先冒泡排序，再找主元素）

算法思想：


对一个序列先进行冒泡排序，变成一个升序排列，遍历这个序列，m记录遍历到的值，count记录该值出现的次数，如果s[i]与m相等，则count++，否则count = 1，m = s[i]，直至出现count > n / 2的情况，返回这个m值。如遍历结束，即说明没有主元素则返回 – 1。

时间复杂度为O(n^2)，空间复杂度为O(1)

#include"head.h";
//冒泡排序：时间复杂度O(n^2),建议用O(nlog2n)的快速排序
void Order(int s[], int n) {
    int sorted = 1;
    int temp;
    for (int j = 0; j < n - 1; j++) { 
        sorted = 1; 
        for (int i = 0; i < n - 1 - j; i++) {
            if (s[i] > s[i + 1]) {
                temp = s[i];
                s[i] = s[i + 1];
                s[i + 1] = temp;
                sorted = 0; 
             }
        }
        if (sorted) { 
            break; 
        }
    }
}

//对排序后的数组查找主元素
int FindMajority1(int s[], int n) {
    int m = s[0], count = 0;
    for (int i = 0; i < n; i++) {
        if (m == s[i]) {
            count++;
        }
        else {
            count = 1;
            m = s[i];
        }
        if (count > n / 2) return m;
    }
    return -1;
}

void main() {
    int n;
    int s[10];
    printf("请输入数组长度:");
    scanf_s("%d", &n);
    printf("请输入数组元素:");
    printf("\n");
    for (int j = 0; j < n; j++) {
        scanf_s("%d", &s[j]);
    }
    Order(s,n);
    printf("主元素为：");
    printf("%d\n", FindMajority1(s,n));
}

3、第三种方法（最优算法）

王道数据结构中最优解答案

算法思想：

1、选取候选的主元素：依次扫描数组中的数，将第一个遇到的数tmp保存在c中，记录tmp出现的次数为1；继续扫描，若下一个数仍等于tmp，则计数+1，否则计数-1，当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，重复上述过程，直到扫描完全部数组元素。

2、判断c是否为真正的主元素：再次扫描数组，统计c出现的次数，若大于n / 2，则为主元素；否则不存在主元素

算法的时间复杂度为O(n)，采用空间复杂度为O(1)

#include"head.h";
int FindMajority2(int R[], int n)
{
    int i, c, count = 1;
    c = R[0];
    for (i = 1; i < n; i++)
        if (R[i] == c)
            count++;
        else
            if (count > 0)
                count--;
            else
            {
                c = R[i];
                count = 1;
            }
    if (count > 0)
        for (i = count = 0; i < n; i++)
            if (R[i] == c)
                count++;
    if (count > n / 2)
        return c;
    else return -1;
}
int main() {
    int n;
    int s[10];
    printf("请输入数组长度:");
    scanf_s("%d", &n);
    printf("请输入数组元素:");
    printf("\n");
    for (int j = 0; j < n; j++) {
        scanf_s("%d", &s[j]);
    }
    printf("主元素为：");
    printf("%d\n", FindMajority2(s, n));
}

输出测试

s[]={0,5,5,3,5,7,5,5}

输出结果：主元素为：5