Boyer-MooreのMajority vote algorithm
(Src/Sequence/MajorityVote.hpp)

• View this file on GitHub
• Last update: 2024-02-06 11:57:20+09:00
• Include: #include "Src/Sequence/MajorityVote.hpp"

使い方

template <class T, class InputIterator>
std::optional<T> MajorityVote(InputIterator first, InputIterator last)

引数に与えたイテレータ範囲[first, last)に過半数を占める要素が存在するなら、その値を返す。存在しない場合はstd::nulloptを返す。

std::optionalはstd::nulloptでないならtrueと評価される。

• cpprefjp std::optional

auto v{MajorityVote<T>(A.begin(), A.end())};
if (v) {
    std::cout << v << '\n';
}
else {
    std::cout << "not exist" << '\n';
}

計算量

長さ $N$ の列に対して $O(N)$ で動作する

参考

• Kyopro Encyclopedia of Algorithms

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• ABC272-G Yet Another mod M (Test/Manual/abc272_g.test.cpp)

Code

#pragma once

#include "../Template/TypeAlias.hpp"

#include <algorithm>
#include <cassert>
#include <optional>
#include <type_traits>

namespace zawa {

template <class T, class InputIterator>
std::optional<T> MajorityVote(InputIterator first, InputIterator last) {
    static_assert(std::is_convertible_v<decltype(*first), T>, "InputIterator must be convertible T");
    assert(first != last);
    std::optional<T> remain{}; 
    usize number{};
    for (auto it{first} ; it != last ; it++) {
        if (number) {
            if (remain.value() == *it) {
                number++;
            }
            else {
                number--;
            }
        }
        else {
            remain = *it;
            number++;
        }
    }
    if (number and 2u * std::count(first, last, remain.value()) > std::distance(first, last)) {
        return remain;
    }
    else {
        return std::nullopt;
    }
}

} // namespace zawa

#line 2 "Src/Sequence/MajorityVote.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Sequence/MajorityVote.hpp"

#include <algorithm>
#include <cassert>
#include <optional>
#include <type_traits>

namespace zawa {

template <class T, class InputIterator>
std::optional<T> MajorityVote(InputIterator first, InputIterator last) {
    static_assert(std::is_convertible_v<decltype(*first), T>, "InputIterator must be convertible T");
    assert(first != last);
    std::optional<T> remain{}; 
    usize number{};
    for (auto it{first} ; it != last ; it++) {
        if (number) {
            if (remain.value() == *it) {
                number++;
            }
            else {
                number--;
            }
        }
        else {
            remain = *it;
            number++;
        }
    }
    if (number and 2u * std::count(first, last, remain.value()) > std::distance(first, last)) {
        return remain;
    }
    else {
        return std::nullopt;
    }
}

} // namespace zawa

Back to top page