Boyer-Moore Majority Vote Algorithm
(misc/majority.hpp)

• View this file on GitHub
• Last update: 2024-01-08 00:27:17+09:00
• Include: #include "misc/majority.hpp"

Description

数列の過半数を占める要素を求める．

• optional<T> majority(vector<T> v)
  • 数列 v の過半数を占める要素を求める
  • 時間計算量: $O(n)$

Reference

• Boyer–Moore majority vote algorithm - Wikipedia
• verify: https://atcoder.jp/contests/abc272/submissions/35557503

Code

#pragma once
#include <optional>
#include <vector>

template <typename T>
std::optional<T> majority(const std::vector<T>& v) {
    T m;
    int cnt = 0;
    for (auto x : v) {
        if (cnt == 0) {
            m = x;
            ++cnt;
        } else if (m == x) {
            ++cnt;
        } else {
            --cnt;
        }
    }
    cnt = 0;
    for (auto x : v) {
        if (m == x) {
            ++cnt;
        }
    }
    return cnt > (int)v.size() / 2 ? std::optional<T>(m) : std::nullopt;
}

#line 2 "misc/majority.hpp"
#include <optional>
#include <vector>

template <typename T>
std::optional<T> majority(const std::vector<T>& v) {
    T m;
    int cnt = 0;
    for (auto x : v) {
        if (cnt == 0) {
            m = x;
            ++cnt;
        } else if (m == x) {
            ++cnt;
        } else {
            --cnt;
        }
    }
    cnt = 0;
    for (auto x : v) {
        if (m == x) {
            ++cnt;
        }
    }
    return cnt > (int)v.size() / 2 ? std::optional<T>(m) : std::nullopt;
}

Back to top page