乐趣区

关于算法:算法2多数投票算法BoyerMoore-Voting-Algorithm及推广

算法 (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] = 1
for key,value in dic.items():
    if value > len(nums)/2:
        return key

2. 排序法

排序后,呈现次数大于一半的必定在两头

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 − 1
Return m

3,Majority Element 的摩尔投票算法求解

num,count = nums[0],0
for x in nums:
    if count == 0:
        num,count = x,1
    elif x == num:
        count += 1
    else:
        count -= 1
return 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
退出移动版