寻找多数元素

今天实现的算法是寻找多数元素，多数元素是指在一个含有n个元素的序列中出现次数多于[n/2]（向下取整）的元素。

蛮力寻找多数元素是对每个元素进行计数，如果某个元素的计数超过[n/2]，则断言它是多数元素，否则不存在多数元素。这种方法的时间复杂度过高，可以寻找更高性能的算法解决这类问题。

如果一个序列存在多数元素，那么该多数元素一定是该序列排序后的中间元素，也就是第[n/2]（向上取整）个元素。所以可以通过寻找一个序列的中间元素，然后判断该元素是否为多数元素来寻找多数元素。对于此方法，有一个结论可以使用：

在原序列中去除两个不同元素后，那么在原序列中的多数元素在新序列中还是多数元素。

这个结论可以支持一个寻找多数元素候选者的算法，该算法的伪代码如下：

算法：CANDIDATE

输入：n个元素的数组A[1...n]

输出：多数元素的候选元素

candidate(m)

?

?
?然后是Java代码：
?
?
?最后是Python实现：
?
#! /usr/bin/env python  # -*- coding:utf-8 -*-class MajorityList:    def __init__(self):        self._list = list()        self.hasMajority = False        self.majority_value = 0        self._list.append(0)    def candidate(self, m):        j = m        c = self._list[m]        count = 1        while j < len(self._list)-1 and count > 0:            j = j + 1            if self._list[j] == c:                count += 1            else:                count -= 1        if j == len(self._list)-1:            return c        else:            return self.candidate(j+1)    def majority(self):        c = self.candidate(1)        count = 0        for j in range(1, len(self._list)):            if self._list[j] == c:                count += 1        if count > (len(self._list)-1)/2:            self.hasMajority = True            self.majority_value = c        else:            self.hasMajority = False            self.majority_value = 0        def add(self, x):        self._list.append(x)        self.hasMajority = False        self.majority_value = 0    def hasMajorityElement(self):        self.majority()        return self.hasMajority    def getMajorityElement(self):        return self.majority_valueif __name__ == '__main__':    a = [1, 2, 5, 5, 5, 4 ,3 ,2, 5, 5, 4, 5, 5]    ml = MajorityList()    print '输入数组为：'    for i in a:        print i,        ml.add(i)    print    result = ml.hasMajorityElement()    print '是否存在多数元素？', result    if result:        print '多数元素为：', ml.getMajorityElement()
?
?