C 计算有序数组的众数

Question

我必须编写一个 C++ 代码来查找数组的中位数和众数。有人告诉我，在对数字进行排序后，查找数组的模式要容易得多。我对功能进行了排序，但仍然找不到模式。

  int counter = 0;
    for (int pass = 0; pass < size - 1; pass++)
        for (int count = pass + 1; count < size; count++) {
            if (array [count] == array [pass])
                counter++;
            cout << "The mode is: " << counter << endl;

原文由 John 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

1.不排序找模式

有人告诉我，在对数字进行排序后，查找数组的模式要容易得多

我不确定。

 std::vector<std::pair<int, unsigned>> mode(const std::vector<int> &v)
{
  if (v.empty())
    return {};

  std::unordered_set<int> seen;

  unsigned max_count(0);
  std::vector<std::pair<int, unsigned>> ret;

  for (auto i(v.begin()); i != v.end(); ++i)
    if (seen.find(*i) == seen.end())
    {
      const auto count(std::count(i, v.end(), *i));

      if (count > max_count)
      {
        max_count = count;
        ret = {{*i, max_count}};
      }
      else if (count == max_count)
        ret.emplace_back(*i, max_count);

      seen.insert(*i);
    }

  return ret;
}

算法

• 使用哈希表 ( seen ) 跳过已经看到的数字；
• 不需要输入向量的副本；
• 只需要一个支持 前向迭代器 的容器。

另请注意，对于较小的输入向量，该函数可以简化为删除哈希表。

你可以在 这里 玩代码。

2.寻找模式排序

std::vector<std::pair<int, unsigned>> mode(std::vector<int> v)
{
  if (v.empty())
    return {};

  std::sort(v.begin(), v.end());

  auto current(*v.begin());
  unsigned count(1), max_count(1);

  std::vector<std::pair<int, unsigned>> ret({{current, 1}});

  for (auto i(std::next(v.begin())); i != v.end(); ++i)
  {
    if (*i == current)
      ++count;
    else
    {
      count = 1;
      current = *i;
    }

    if (count > max_count)
    {
      max_count = count;
      ret = {{current, max_count}};
    }
    else if (count == max_count)
      ret.emplace_back(current, max_count);
  }

  return ret;
}

我们假设一个未排序的输入向量，因此该函数适用于已排序和处理的原始向量的副本。

如果原始向量已经排序，则可以通过引用传递输入参数，并且可以删除 std::sort 调用。

你可以在 这里 玩代码。

表现

性能取决于多个因素（输入向量的大小、值的分布……）。

例如，如果输入整数的范围很小， 算法 1 比 算法 2 快。

你可以 在这里 做实验。

原文由 manlio 发布，翻译遵循 CC BY-SA 4.0 许可协议