求一个序列中的主元素

佚名 4年前 (2020-03-31) 算法 1593人围观抢沙发百度已收录

问题(2013 统考408真题）：已知一个整数序列A = (a₀,a₁,...,a_n-1), 其中0≤a_i≤n (0≤i<n)。若存在a_p1=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。

解答：

算法设计思想：从头扫描数组，标记可能出现的主元素。最后对该标记的主元素num计数，确定其是否为主元素。
步骤：
- 将第一个出现的元素num保存到c中，用count记录num出现的次数，初始时令count = 1。如果下一个遇到的元素仍然是num则将count加1，否则将count减1。如果此时count == 0，则将下一个元素保存到c中，并重置count为0。重复上述过程，直至扫描完全部元素。
- 判断此时的c是否为真正的主元素。统计c出现的次数，并保存到count中，如果count > n / 2，则是主元素，否则不是。
算法的正确性：
- 对于这样一个序列，去除其中任意两个不相等的元素，在剩下的元素中，如果存在主元素，主元素出现的次数仍然大于n / 2。
- 使用count进行计数时，当count == 0时，一定有偶数个的元素与可能的主元素进行了比较，这偶数个元素中一半是可能的主元素，另一半是其他数。
复杂度：T(n) = O(n), S(n) = O(1)。

算法实现：

int Majority(int A[], int n)
{
	int i, c, count = 1;
	c = A[0];
	for (i = 1; i < n; i++)
	{
		if (A[i] == c)
		{
			count++;
		}
		else
		{
			if (count > 0)
			{
				count--;
			}
			else
			{
				c = A[i];
				count = 1;
			}
		}
	}
	if (count > 0)
	{
		count = 0;
		for (i = 0; i < n; i++)
		{
			if (A[i] == c)
			{
				count++;
			}
		}
	}
	if (count > n / 2)	return c;
	else return -1;
}