c++ - 在 C++ 中查找数组的模式(最常见的元素)

Question

我在一个面试问题上有这个。我想看看 StackOverflow 会怎么做。

Bjarne Stroustrop 会如何看待我的方式？有点罗嗦，但不幸的是，我不知道如何让它变得更好。我知道你们会 mock 我的愚蠢。

template <class T>
T mode(T* arr, size_t n)
// If there's a tie, return an arbitrary element tied for 1st
// If the array size is 0, throw an error
{
   if (n == 0)
   {
       throw("Mode of array of size 0 is undefined, bro.");
   }
   else if (n == 1)
   {
       return arr[0];
   }
   else 
   {
      std::pair<T, int> highest(arr[0], 1);
      std::map<T, int> S;
      S.insert(highest);
      for (T* thisPtr(arr + 1), lastPtr(arr+n); thisPtr != lastPtr; ++thisPtr)
      {
          if (S.count(*thisPtr) == 0)
          {
             S.insert(std::pair<T, int> (*thisPtr, 1);
          }
          else 
          {
             ++S[*thisPtr];
             if (S[*thisPtr] > highest.second)
             {
                 highest = std::pair<T, int> (*thisPtr, S[*thisPtr]);
             }
          }
      }
   }
}

Answer 1

你可以这样做，前提是 T 实现了 std::hash:

std::unordered_multiset<T> elems;
std::for_each(arr, arr + size, [&elems](T const & elem) { elems.insert(elem); }

//Now you have elems.count() for each entry
auto max_count = /*Guaranteed minimum value*/
T mode{};
for (auto const & set_elem : elems) {
    if (max(elems.count(set_elem), max_count) == max_count)) {
      mode = set_elem;
    }
}