寻找多数元素
今天实现的算法是寻找多数元素，多数元素是指在一个含有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()??
