sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "misc/majority.hpp"
数列の過半数を占める要素を求める.
optional<T> majority(vector<T> v)
v
#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; }