寻找主元素算法

问题:
大小为N的数组A,其主元素是一个出现超过N/2次的元素,请你找出数组A的主元素。

算法描述:
想象自己的手依次查看数组A的每个元素,每次查看一个元素。 如果手上没有数,则取出手指指向的当前的数放在手上; 如果手上有数,则把当前指向的数和手上的数比较,若相同则放在手里(因此手里的数可能会很多,但都是相同的),若不同则取手里的一个数和当前指向的数一起扔掉(所谓临死还要拖一个下水的…)。

到最后,手里剩下的数,就是主元素,若没有数则该数组无主元素。

上述应该只是个过程的描述,其思想大概如下:若数组存在主元素X,则在数组中每次剔除两个不同的数,剩下的数中主元素仍是X。 其实这种思想很常见,比如红黑两方士兵,双方单位兵力相当,但红方数量占优势,那么红黑双方每次各出一个兵火拼,每次都两败俱伤死一对,最后剩下的肯定还是红方士兵。= =

注:算法非原创,只是换着法表述外加记录

Published: February 04 2013