Finding exactly N consecutives in a sorted list

Question

I recently stumbled upon a little problem.

Part of an algorithm I was working on needed to find n consecutive numbers in a sorted list of numbers.

So, for example, the list would look something like this:

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

Given that list and N, the amount of consecutive duplicates, the algorithm needed to find the first number in the smallest group of exactly N consecutive numbers. So for example with N = 2 and the given list, the algorithm should find "2". With N = 3 it should pass the group of 2's, find the group of 5's instead since it's the smallest group of 3 consecutive duplicates in that list. It shouldn't return 9 since there are actually 4 consecutive 9's and with N = 3 we are looking for the smallest group of exactly 3 consecutives.

I did in the end cobble together some peace of crap code that did the job, but I was wondering how would some experienced programmer do this. Utilizing as much of the C++11 Style of Code advertised by Stroustroup himself and using as much of the C++11 STL for correctness, portability and compactness for reasoning.

Answer 1

If speed doesn't matter:

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();
}