算法(2)-少数投票算法(Boyer-Moore Voting Algorithm)及推广
摩尔投票算法也能够叫做少数投票算法，是我在看到 leetcode 169（Majority Element）题目时看到的算法。
这篇文章从 leetcode 169（Majority Element）登程解说摩尔投票算法的原理和劣势，同时从 leetcode 229（Majority Element2）登程解说摩尔投票算法的改良和推广。（本文所有代码都是python代码）
一、Majority Element题目介绍
给定一个长度为n的数组的时候，找出其中的主元素，即该元素在数组中呈现的次数大于n/2的取整。题目中曾经假设所给的数组肯定含有元素，且主元素肯定存在。一下是一些罕用办法：
1.用字典遍历每个元素，并计数
dic = {}for x in nums: if x in dic: dic[x] += 1 else: dic[x] = 1for key,value in dic.items(): if value > len(nums)/2: return key2.排序法
排序后，呈现次数大于一半的必定在两头
nums.sort()return nums[len(nums)//2]二、摩尔投票算法
摩尔投票算法的工夫和空间都很低，工夫复杂度为O(n)，空间复杂度为O(1)，这也是抉择遮蔽算法的起因。
1.算法原理
每次从数组中找出一对不同的元素，将它们从数组中删除，直到遍历残缺个数组。因为这道题曾经阐明肯定存在一个呈现次数超过一半的元素，所以遍历完数组后数组中肯定会存在至多一个元素。
- 算法在局部变量中定义一个序列元素(m)和一个计数器(i)，初始化的状况下计数器为0；
- 算法顺次扫描序列中的元素，当解决元素x的时候，如果计数器为0，那么将x赋值给m，而后将计数器(i)设置为1；
- 如果计数器不为0，那么将序列元素m和x比拟，如果相等，那么计数器加1，如果不等，那么计数器减1。
- 解决之后，最初存储的序列元素(m)，就是这个序列中最多的元素。
（如果不确定是否存储的元素m是最多的元素，还能够进行第二遍扫描判断是否为最多的元素）
总结起来，核心思想就是，少数元素因为其个数超过了n/2，所以用一个少数元素和对消一个其余元素，那么剩下肯定是少数元素，如果对消过程中，有其余元素和其余元素对消了，那么就会剩下更多的少数元素。
2，算法伪代码
初始化元素m=0,计数器count=0;遍历数组中的每个数x: if i = 0: m = x and count = 1 else if m = x: count = count + 1 else: count = count − 1Return m3，Majority Element的摩尔投票算法求解
num,count = nums[0],0for x in nums: if count == 0: num,count = x,1 elif x == num: count += 1 else: count -= 1return num三、摩尔投票算法的改良
1.题目：LeetCode 229 [Majority Element II]
给定一个整型数组，找到所有主元素，它在数组中的呈现次数严格大于数组元素个数的三分之一。
算法：每次删除三个不雷同的数，最初留下的肯定是呈现次数超过1/3的数，这个思维能够推广到呈现次数超过1/k次的元素有哪些。
- 因为呈现次数大于n/3的元素最多只有两个，所以最开始能够保护两个数字(num1,num2)和两个计数器(counter1,counter2)；
- 遍历数组，当数组中元素和num1或者num2雷同，对应的counter1或者counter2加1；
- 如果counter1或counter2为0，将遍历到的该元素赋给num1或者nums2；
- 否则counter1和counter2都减1。
2.python代码
num1,count1 = None,0 num2,count2 = None,0 for x in nums:# 算法外围，找出次要元素的候选值 if x == num1: count1 += 1 elif x == num2: count2 += 1 elif count1 == 0: num1,count1 = x,1 elif count2 == 0: num2,count2 = x,1 else: count1 -= 1 count2 -= 1 count1,count2 = 0,0 for x in nums:# 统计确定候选值是真的次要元素 if x == num1: count1 += 1 if x == num2: count2 += 1 res = [] if count1 > len(nums)//3: res.append(num1) if count2 > len(nums)//3: res.append(num2) return res