()
'''在O(n)时间复杂度,O(1)空间复杂度内,判断是否有候选人的得票数过半
该算法在运行过程中,需要两个临时变量c和t,c记录当前可能得票数过半的候选人编号,t记录该候选人的净超出次数。对于c而言,除了可以等于1~m中的任何值之外,还有另一种状态,我们把其叫做未知状态,用于表示当前任何候选人的得票数都不可能过半(程序中可以用0,或者-1表示),t的最小值为0,程序开始运行时c为未知状态(c=0),t=0,然后按照如下方法处理投票数组v。
- 对于v[i](1<=i<=n),如果c此时为未知状态,则c=v[i],t=1,递增i。
- 如果c==v[i],++t,递增i。
- 如果c!=v[i],--t,如果t==0,将c置为未知状态,递增i。
- 所有投票处理完毕后,如果c为未知状态,则说明不存在任何候选人的得票数过半,否则重新遍历数组v,统计候选人c的实际得票总数,如果c的得票数确实过半,则c就是最终结果。'''
如果有人票数过半,c最终状态一定大于0.
如果c最终大于0, 不一定有人票数过半。