c++ - 在排序列表中恰好找到 N 个连续的

Question

我最近偶然发现了一个小问题。

我正在研究的部分算法需要在已排序的数字列表中找到 n 个连续数字。

因此，例如，列表看起来像这样:

1 2 2 3 4 5 5 5 6 7 8 9 9 9 9

给定该列表和 N(连续重复的数量)，算法需要在恰好 N 个连续数字的最小组中找到第一个数字。因此，例如对于 N = 2 和给定的列表，算法应该找到“2”。当 N = 3 时，它应该通过 2 组，找到 5 组，因为它是该列表中最小的 3 个连续重复组。它不应该返回 9，因为实际上有 4 个连续的 9，并且在 N = 3 的情况下，我们正在寻找正好 3 个连续的最小组。

我最终拼凑了一些完成这项工作的废话代码，但我想知道一些有经验的程序员会如何做到这一点。使用尽可能多的 C++11 代码风格 advertised by Stroustroup himself并使用尽可能多的 C++11 STL 来实现推理的正确性、可移植性和紧凑性。

Answer 1

如果速度不重要:

template <class T >
T firstOfN( std::vector<T> list, unsigned N ){
  std::multiset<T> mset( list.begin(), list.end() );
  for( typename std::multiset<T>::iterator it = mset.begin(); it != mset.end(); ++it ){
    if( mset.count( *it ) == N ) return *it;
  }
  throw std::exception();
}