摩尔投票算法

Posted on | Edited on | In

问题

给定一个整型数组，打印其中出现次数大于一半的数。（假设出现次数大于一半的数一定存在）

思路

直接想法：采用Hash表存储每个数字出现的次数，遍历一遍Hash表即可得到结果。
时间复杂度：O(n)
空间复杂度：O(n)

更优的解法：摩尔投票算法（Boyer-Moore Voting Algorithm）

算法原理

每次从数组中找出一对不同的元素，将其从数组中删除，直到找不到不同的元素。数组中剩下的元素即为结果。
时间复杂度：O(n)
空间复杂度：O(1)

算法步骤

  1. 定义元素res, 计数器count；
  2. 遍历数组nums中的元素：
    • count = 0: res = nums[i];
    • res == nums[i]: count++;
    • res != nums[i]: count–;
  3. 遍历结束，res存储的元素值即为数组中出现次数大于一半的数。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int majorityElement(vector<int>& nums) {
    int res = 0;
    int count = 0;
    int size = res.size();

    for (int i = 0; i < size; i++) {
        if (count == 0) {
            res = nums[i];
        }
        else if (res == nums[i]) {
            count++;
        }
        else {
            count--;
        }
    }
    return res;
}

问题进阶

给定一个整型数组，其元素个数为N，给定一个整数K，打印其中出现次数大于N/K的数。如果没有这样的数，打印提示信息。

问题分析

两个不同：

  1. 要得到的是数组中出现次数超过N/K的元素；
  2. 可能不存在满足条件的解；

同样利用摩尔投票算法，每次取K个不同的元素，删除，直到数组中不存在K个不同的元素为止。
时间复杂度：O(N*K)
空间复杂度：O(K)

算法步骤

  1. 定义一个HashMap， 用于存储候选元素以及候选元素对应的计数器
  2. 遍历数组nums中的元素：
    • 如果nums[i] 在HashMap中，HashMap[nums[i]]++;
    • 否则:
      • 如果HashMap的size大于K-1， 所有的HashMap值减1。如果HashMap值为0， 删掉该pair
      • 否则，将pair(nums[i], 1)加入HashMap；
  3. 找到HashMap中大于0的元素，即为结果