Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <array>
- #include <type_traits>
- #include <stdexcept>
- #include <algorithm>
- /*! \brief get the number(count > 1/2) in array
- \note complexity time-O(N) space-O(1)
- */
- template <typename ITEM, std::size_t N>
- ITEM max(const std::array<ITEM, N>& a) {
- if (3 > a.size()) {
- throw std::invalid_argument("Too shorter array.");
- }
- int flag = 1;
- int target = a[0];
- for (std::size_t i = 0; i < a.size() - 1; i++) {
- if (a[i] != a[i+1]) {
- flag--;
- } else {
- flag++;
- if (0 > flag) {
- target = a[i];
- flag = 1;
- }
- }
- }
- // check
- std::size_t count = std::count(a.begin(), a.end(), target);
- if (count*2 <= a.size()) {
- throw std::invalid_argument("Not suitable input array.");
- }
- return target;
- }
Add Comment
Please, Sign In to add comment