灵光一现

灵光一现

主元素

• 主元素
  • 主元素的定义
  • 寻找主元素
    • 直接寻找
      • 改进
    • 排序后寻找
    • 灵光一现
  • 补充

主元素的定义:

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

寻找主元素

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

直接寻找

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

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

代码略

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

改进

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

代码如下:

 #define MAX 1000int 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(N)$,但空间效率却变成了 O(MAX) $O(MAX)$,适合在已知范围,而且范围相对较小的情况使用.

排序后寻找

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

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

那么接下来就很简单了.

代码略

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

灵光一现

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

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

//#######################################################################
//# Author: izualzhy@163
//# 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++;elserepeatTimes--;}}return mainElement;
}

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

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

补充

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

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

1 1 1 1 0 0 0 0

那么谁是主元素呢?

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