摘要
这篇文章由投票问题引出，讨论了几种找出占多数元素的算法，并给出最终算法的源代码和递归调试过程，最后提出改进方案。
(一) 问题描述
在选举投票中，常常有这样的规定：如果投某个选项的次数超过全部可投票的一半，那么最终结果就为该选项，否则，此次投票无效。
我们将此问题抽象成数学模型。假设投票结果为长度为n整数序列A，像这样[A[0],A[1],...A[n-1]]，如果某个元素的出现次数大于(n/2)，就可以断定它是多数元素c；否则，没有多数元素。
(二) 算法分析
有几种算法可以解决这个问题，最蛮力的是，把每一个元素（n个）通过与其他元素比较（n-1次），这样的时间复杂度是Θ(n²)，代价太大。如果先排序，再按上述方法计算，则最坏情况下时间复杂度为Θ(n㏒n)。
另一种更聪明方法是看作排序问题，先对A排序，因为多数元素占比超过一半，可以很容易地证明，中间值就是c。这个方法排序时间复杂度Θ(n㏒n)，搜索中间值Θ(n)，总的为Θ(n㏒n)+ Θ(n)。这个算法隐藏的常数太大，不够鲁棒。
还有一种方案，使用一个hash表，对数组进行一趟扫描统计每个元素出现的次数，即可得到多数元素。时间复杂度O(n)，空间复杂度O(n)。
像上面这样的算法，遇到全民公投这种大规模数据的处理需求，相当无力、虚弱，等待的时间太久了，以至于引起选民不满，弹性云计算按资源开销收费，老板也不开心。
我们发现这样一个规律，从序列中同时除去两个不同元素，类似于抵消，多数元素仍然占多数。假设A=[8, 8, 8, 2, 0, 8, 7, 10, 2, 8, 7, 8, 8, 8, 2]，取c=A[0]，经过一次抵消→[2, 8, 7, 8, 8, 8, 2]，c=2，这个抵消这样设计，如果遇到相同的，就算到一起，不同的就减去一个计数，当计数count为0，意味着前面全部抵消完了，而不是按规律中僵化地非得找一个不同数据一起移除，→[7, 8, 8, 8, 2] →[8, 8, 2] →返回8，其它元素湮灭后剩余的“众数”。然后遍历一遍A，看count是否大于7,是的话就是多数元素。
这就是这个更漂亮的算法，Θ(n)和Θ(1)的时间和空间复杂度。
(三) 编程实现
编程语言Python3.5，依赖random库生成数据。
n=len(A) # 序列长度
def candidate(m):
j=m # 工作索引
c=A[m] # 候选/被比较的候选众数
count=1# 计数器
while j<n and count >0:
j+=1
# 如果现在的j使得列表越界，可以执行else的操作并退出循环
try:
A[j]
except IndexError:
count -= 1
continue
# 有一个一样计数器+1
if A[j]==c:
count+=1
# 不一样的抵消，计数器-1
else:
count-=1
# 工作索引和长度一样，走完序列，返回当前剩余的候选众数
if j==n:
return c
else:
return candidate(j+1)
def MAJORITY():
c=candidate(0)
count=0
# 众数的出现次数
for j in range(0,n):
if A[j]==c:
count+=1
# 是否超过一半
if count>(n/2):
return c
else:
return None
pass
(四) 举例演示递归过程
图一
中间3个变量A，n分别为传入数据和长度。
图 1
图二
c，count，j，m分别为候选数，计数器，工作索引，初始索引。
c=A[m]，count由于前面一段(0~9)10个抵消变为0，所以递归调用下一层，下一层的初始工作索引j+1。
图 2
图三
可以看到和上一个格式一样，状态一样，即将进入“黑洞”。
图 3
图四
这一层j和n相等为16，结束遍历，所以还剩下一个活口的候选值8（画圈的）将被返回到上一个“宇宙”，接下来就逐层返回。
图 4
(五) 总结与改进
通过投票问题我们研究并实践了寻找多数数的算法，更进一步，该算法可以用并行实现，其基本思想为对原数组采用分治的方法，把数组划分成很多段(每段大小可以不相同)，在每段中计算出candidate-count二元组，然后得到最终结果。
举个例子，原数组为[1,1,0,1,1,0,1,0,0] 划分1：
[1,1,0,1,1] –> (candidate,count)=(1,3)
划分2：[0,1,0,0] –> (candidate,count)=(0,2) 根据(1,3)和(0,2)可得，原数组的多数元素为1。
正因为这个特性，考虑若要从一个非常大的数组中寻找多数元素，数据量可能多大数百G，那么我们甚至可以用MapReduce的方式来解决这个问题。
参考资料
所有代码
import random
'''
A为有n个整数元素的列表
'''
choose=1# 0:生成数据 1:全部运算 2:调试递归（需要用IDE）
all_A=[
[8, 8, 8, 2, 0, 8, 7, 10, 2, 8, 7, 8, 8, 8, 2],
[9, 9, 9, 9, 9, 9, 9, 9, 9, 7, 9, 3, 9, 7, 3, 9],
[6, 2, 2, 4, 2, 3, 2, 2, 5, 2, 2, 2, 2, 6, 2, 2, 5, 2],
[8, 8, 8, 8, 6, 8, 5, 6, 0, 0, 4, 4, 8, 6, 8, 8],
[3, 4, 10, 10, 4, 4, 4, 7, 4, 4]
]
def candidate(m):
j=m # 工作索引
c=A[m] # 候选/被比较的候选众数
count=1# 计数器
while j<n and count >0:
j+=1
# 如果现在的j使得列表越界，可以执行else的操作并退出循环
try:
A[j]
except IndexError:
count -= 1
continue
# 有一个一样计数器+1
if A[j]==c:
count+=1
# 不一样的抵消，计数器-1
else:
count-=1
# 工作索引和长度一样，走完序列，返回当前剩余的候选众数
if j==n:
return c
else:
return candidate(j+1)
pass
def MAJORITY():
c=candidate(0)
count=0
# 众数的出现次数
for j in range(0,n):
if A[j]==c:
count+=1
# 是否超过一半
if count>(n/2):
return c
else:
return None
pass
if choose==1:
for A in all_A:
# 序列长度
n=len(A)
# print(n)
print(MAJORITY())
if choose==0:
A=[]
for i in range(5):
b=[]
for j in range(5):
r=random.randint(0,10)
for c in range(random.randint(1,3)):
b.append(r)
A.append(b)
for i,a in enumerate(A):
t = a[random.randint(0,len(a)-1)]
for j in range(len(a)//2):
a.append(t)
a=random.shuffle(a)
for a in A:
print(str(a)+',')
if choose==2:
A=all_A[3]
del all_A
n=len(A)
print(MAJORITY())
'''
8
9
2
None
4
'''
网友评论