LeetCode百题刷002摩尔投票法

遇到的问题都有解决的方案，希望我的博客可以为你提供一些帮助

图片源自leetcode 

题目：169. 多数元素 - 力扣（LeetCode）

一、排序法

题目要求需要找到多数值（元素个数>n/2）并返回这个值。一般会想到先排个序，再取中间值；因为在有序数组中多数值（元素个数>n/2）的中间值必定是多数值。

代码如下：

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};

复杂度分析 

时间复杂度：

使用的排序算法时间复杂度是

空间复杂度：

 在原数组上排序，无额外空间开销

结果

二、哈希表法

一个比较常规的思路是：对于每一个元素我可以记录它出现的次数，最后返回出现次数最多的元素就行。这样问题就变成了如何在无序的数组中精确的识别出每一个元素，并且记录他们出现的次数。哈希表天然适配，哈希表提供key-value键值映射，key可用于记录数组中的元素，value可用于累计出现的次数。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        ans={}
        for num in nums:
            ans [num]=ans.get(num,0)+1
        return max(ans,key=ans.get)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int ,int> ans;
        int n=nums.size();
        for (auto num :nums)
        {
            ans[num]++;
            if (ans[num]>n/2)
            {
                return num;
            }
        }
        return -1;
    }
};

复杂度分析：

 时间复杂度：只需要遍历一次数组

空间复杂度：最坏情况下需要与元素组等大的空间，但在本题目中明确指出了多数元素是存在的所以最多需要空间不大于 n/2

 三、摩尔投票法（Boyer-Moore Voting Algorithm）

1. 基本思想

摩尔投票法是一种用于 快速寻找数组中出现次数超过一定比例的元素 的算法。其核心思想是通过 “抵消” 策略，在遍历数组时维护候选元素及其计数，最终找到可能的众数。

• 经典问题：在数组中找出出现次数超过 n/2 的元素（即严格众数）。

• 扩展问题：找出所有出现次数超过 n/k 的元素（如 k=3，找出出现次数超过 n/3 的元素）。

2. 算法步骤（以寻找严格众数为例）

1. 初始化：
   设置候选元素 candidate 和计数器 count，初始值为 None 和 0。

2. 遍历数组：
   对每个元素 num：

   • 如果 count == 0，设当前元素为候选（candidate = num）。

   • 如果 num == candidate，计数器加一（count += 1）。

   • 否则，计数器减一（count -= 1）。

3. 验证结果：
   最终需再次遍历数组，确认 candidate 的出现次数是否超过 n/2。

3. 示例分析

以数组 nums = [3, 2, 3] 为例，寻找严格众数（出现次数 > 3/2 = 1.5，即至少出现 2 次）：

最后验证 3 出现 2 次，满足条件。

4. 扩展：寻找出现次数超过 n/k 的元素

若需找出所有出现次数超过 n/k 的元素（例如 k=3），需维护 k-1 个候选元素及其计数器。

步骤：

1. 初始化：
   维护 k-1 个候选和计数器，如 candidate1, count1 和 candidate2, count2（当 k=3 时）。

2. 遍历数组：

   • 若当前元素与任一候选相同，对应计数器加一。

   • 若不同且某计数器为 0，替换候选并重置计数器为 1。

   • 否则，所有计数器减一。

3. 验证候选：
   统计所有候选的实际出现次数，确认是否超过 n/k。

5. 对于本题目而言如何应用

思路：
多数元素出现次数大于数组长度一半，利用抵消思想，每次找到两个不同元素就抵消掉，最后剩下的就是多数元素。遍历数组，维护一个候选元素 candidate 和其出现次数 count 。遇到相同元素，count 加 1；遇到不同元素，count 减 1 ，若 count 为 0 ，更新 candidate 为当前元素并将 count 设为 1 。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
         candidate = None
         count = 0
    
        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
    
        # 验证
        return candidate if nums.count(candidate) > len(nums) // 2 else -1

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int condidate =NULL;
        int count=0;
        for (auto num:nums)
        {
            if (count==0)
            {
                condidate=num;
            }
            count=count++?condidate==num:count--;

        }
        return condidate;
    }
};

寻找出现次数超过 n/3 的元素

def majorityElement_3(nums):
    candidate1, count1 = None, 0
    candidate2, count2 = None, 0
    
    for num in nums:
        if num == candidate1:
            count1 += 1
        elif num == candidate2:
            count2 += 1
        elif count1 == 0:
            candidate1, count1 = num, 1
        elif count2 == 0:
            candidate2, count2 = num, 1
        else:
            count1 -= 1
            count2 -= 1
    
    # 验证候选
    res = []
    for c in [candidate1, candidate2]:
        if nums.count(c) > len(nums) // 3:
            res.append(c)
    return res

结果：

6. 复杂度分析

• 时间复杂度：O(n)
  仅需两次遍历数组（第一次找候选，第二次验证）。本题中只需遍历一次，不需要验证（题干条件已给出一定有多数元素）。

• 空间复杂度：O(1)
  仅需常数空间存储候选和计数器。

7. 与其他方法对比

摩尔投票法可以在线性时间和常数空间内高效解决多数元素问题，尤其适合处理大规模数据或内存受限的场景。