BoyerMoore majority vote algorithm

發表於 Disqus：
文章字數： 1.4k 所需閱讀時間 ≈ 1 分鐘

刷題的時候遇到 BoyerMoore majority vote algorithm 相關問題，特別寫一篇記錄

問題描述

leetcode 題目

給 N 個數字，找出出現次數超過 ⌊n / 2⌋ 的數字

解法

因為題目要求超過 ⌊n / 2⌋

所以 [1,1,2,2] 這個 case，⌊n / 2⌋ 為 2，沒有任何一個數字超過 2，所以沒有答案

但題目保證一定有 majority element，所以不用擔心這種狀況

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int majorityElement(int* nums, int numsSize){
    int i, num = 0, count = 0;
    for(i = 0; i < numsSize; i++) {
        if (count == 0) {
            num = nums[i];
            count = 1;
        }
        else if(nums[i] == num) {
            count++;
        }
        else {
            count--;
        }
    }
    return num;
}

變形

leetcode 題目

給 N 個數字，找出出現次數超過 ⌊n / 3⌋ 的數字

同理，因為題目要求超過 ⌊n / 3⌋

所以 [1,1,2,2,3,3] 這個 case，⌊n / 3⌋ 為 2，沒有任何一個數字超過 2，所以沒有答案

但這次題目沒有保證一定有 majority element，所以最後要檢查 count 有沒有滿足條件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int* majorityElement(int* nums, int numsSize, int* returnSize){
    int i, count1 = 0, count2 = 0, num1 = 0, num2 = 0;
    for(i = 0; i < numsSize; i++) {
        if(nums[i] == num1) {
            count1++;
        }
        else if(nums[i] == num2) {
            count2++;
        }
        else if(count1 == 0) {
            num1 = nums[i];
            count1 = 1;
        }
        else if(count2 == 0) {
            num2 = nums[i];
            count2 = 1;
        }
        else {
            count1--;
            count2--;
        }
    }
    
    count1 = 0, count2 = 0;
    for(i = 0; i < numsSize; i++) { 
        if(nums[i] == num1) {
            count1++;
        }
        else if(nums[i] == num2) {
            count2++;
        }
    }
    
    int *ans = calloc(2, sizeof(int));
    (*returnSize) = 0;
    if(count1 > numsSize / 3) {
        ans[(*returnSize)++] = num1;
    }
    if(count2 > numsSize / 3) {
        ans[(*returnSize)++] = num2;
    }
    return ans;
}

參考連結

  1. Boyer–Moore majority vote algorithm