daily pastebin goal
15%
SHARE
TWEET

Untitled

a guest Dec 9th, 2018 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <array>
  3. #include <type_traits>
  4. #include <stdexcept>
  5. #include <algorithm>
  6.  
  7. /*! \brief get the number(count > 1/2) in array
  8.     \note complexity time-O(N) space-O(1)
  9. */
  10. template <typename ITEM, std::size_t N>
  11. ITEM max(const std::array<ITEM, N>& a) {
  12.         if (3 > a.size()) {
  13.                 throw std::invalid_argument("Too shorter array.");
  14.         }
  15.         int flag = 1;
  16.         int target = a[0];
  17.         for (std::size_t i = 0; i < a.size() - 1; i++) {
  18.                 if (a[i] != a[i+1]) {
  19.                         flag--;
  20.                 } else {
  21.                         flag++;
  22.                         if (0 > flag) {
  23.                                 target = a[i];
  24.                                 flag = 1;
  25.                         }
  26.                 }
  27.         }
  28.  
  29.         // check
  30.         std::size_t count = std::count(a.begin(), a.end(), target);
  31.         if (count*2 <= a.size()) {
  32.                 throw std::invalid_argument("Not suitable input array.");
  33.         }
  34.         return target;
  35. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top