灵光一现--寻找主元素

时间：2020-11-29 21:32:58

主元素

主元素的定义:

如果一个数组A[1..n]中超过半数的元素都相同时，该数组被称为含有主元素。

寻找主元素

  • 那么如何寻找一个数组的主元素么?

直接寻找

虽然这是个笨方法,但笨方法也有他的好处:好懂,易写.

定义不是说了么,数量超过一半的数就是主元素,那么我们统计每个数出现的次数不就好了.

代码略

这个算法的时间效率为 O(N2) ,空间效率为 O(N) ,但好写易用,适合在不需要时间和效率的地方使用.

改进

当已知元素的范围,我们可以用数组下标来对应元素,以快捷的统计元素的个数.

代码如下:

 #define MAX 1000
int FindMainElement(int *Num,int N)
 {
int Count[MAX]={0};
for(int i=0;i<N;i++)//统计个数
     Count[Num[i]]++;
for(int i=0;i<N;i++)//找出主元素
if(Count[Num[i]]>=N/2)
return Count[Num[i]];
 }

相比刚才的算法,时间效率变为 O(N) ,但空间效率却变成了 O(MAX) ,适合在已知范围,而且范围相对较小的情况使用.

排序后寻找

既然已经知道了主元素一定多于 N/2 个,那么我们可以知道,将元素按照相同在一起排列时,那么N/2这个元

素一定是组元素,那么这种排列最常见的莫过于排序了.

那么接下来就很简单了.

代码略

算法的时间效率和空间效率由排序算法而定,那么我么可以知道,该种算法最好的是 O(NlogN) 的时间效率,和 O(1) 的空间战用,如果没有接下来的算法,那么这种算法无疑是最好的.

灵光一现

有些算法无法用常用的算法思想来归纳他,他们往往来自脑海中一现的火花,令人深深折服.

以下算法来自于<编程之美>

//#######################################################################
//# Author: izualzhy@163.com
//# Description: 
//#######################################################################

int FindMainElement(const int a[], const int Len)
{
int mainElement;
int repeatTimes = 0;
for ( int i=0; i<Len; ++i) {
if (repeatTimes==0) {
            mainElement = a[i];
            repeatTimes = 1;
        } else {
if (a[i]==mainElement)
                repeatTimes++;
else
                repeatTimes--;
        }
    }
return mainElement;
}

如果你看不懂,那么看完下面这个小故事,你一定会懂:

主元素杯–最强团队争霸赛又开始了,一群团队摩拳擦掌,跃跃欲试,现在他们鱼贯而入,但是一点点意外,使他们的顺序发生了混乱,并非是按照同意团队入场,主办方想了个巧妙地方法,因为按夺冠的要求来看,胜出的团队人数一定大于等于参赛人数的一半,那么把每个参赛选手都变成相同的实力,那么只要不内斗,夺冠队伍一定可以打过其余的所有队伍,最后站在擂台上的最后一定就是夺冠队伍了,最终这一届争霸赛成功举办,大家纷纷赞叹主办方的机智.

补充

有种主元素的定义包括了半数的情况,这将带来非常麻烦的情况:

只要半数就可以了,那么是如下情况呢?

1 1 1 1 0 0 0 0

那么谁是主元素呢?

这样的话解决这个问题就麻烦的多,至少函数可能不能传回一个数,那么遇到这种情况,请大家发挥自己找出最合适的方法吧.

标签：

相关文章