Finding spaces in a sequence of numbers

Question

I have a std :: vector containing several numbers that are not in any particular order, and may or may not have spaces between numbers - for example, I can have {1,2,3, 6} or {2, 8,4,6} or {1, 9, 5, 2}, etc.

I would just like to look at this vector and say "give me the lowest number> = 1 that does not appear in the vector." So,

for the three examples above, the answers will be 4, 1, and 3, respectively.

This is not critical performance, but the list is short, so there is no problem copying the list and sorting it, for example.

I really don't stick with the way to do this, but my STL skills are seriously atrophied, and I feel like I'm going to do something inappropriate - I would be interested to know what other people came up with.

Answer 1

The verified answer uses <for comparison.! = Is much simpler:

int find_gap(std::vector<int> vec) { std::sort(vec.begin(), vec.end()); int next = 1; for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) { if (*it != next) return next; ++next; } return next; } find_gap(1,2,4,5) = 3 find_gap(2) = 1 find_gap(1,2,3) = 4 

I do not pass a link to the vector, because a) he said that time does not matter, and b) so I do not change the order of the original vector.

Answer 2

The standard algorithm you are looking for is std :: adj_find

Here is a solution that lambda also uses to make the predicate clean:

 int first_gap( std::vector<int> vec ) { // Handle the special case of an empty vector. Return 1. if( vec.empty() ) return 1; // Sort the vector std::sort( vec.begin(), vec.end() ); // Find the first adjacent pair that differ by more than 1. auto i = std::adjacent_find( vec.begin(), vec.end(), [](int l, int r){return l+1<r;} ); // Handle the special case of no gaps. Return the last value + 1. if ( i == vec.end() ) --i; return 1 + *i; } 

Answer 3

Sorting the list and then doing a linear search seems to be the easiest solution. Depending on the expected list structure, you can use a less general-purpose sorting algorithm, and if you implement sorting yourself, you can track the data during sorting, which can be used to speed up (or completely eliminate) the search stage. I do not think there is a particularly elegant solution to this problem.

Answer 4

You can select a bit vector (the same length as the input vector), initialize it to zero, and then mark all the indices that occur (note that numbers that exceed the length can be ignored). Then return the first unlabeled index (or length, if all indexes are marked, which happens only if all indexes occur exactly once in the input vector).

This should be asymptotically faster than sorting and searching. It will use more memory than sorting if you are allowed to destroy the original, but less memory than sorting if you must save the original.

Answer 5

Sort and search:

 std::sort(vec.begin(), vec.end()); int lowest = 1; for(size_t ii = 1; ii < vec.size(); ++ii) { if (vec[ii - 1] + 1 < vec[ii]) { lowest = (vec[ii - 1] + 1); break; } } /* 1, 2, ..., N case */ if (lowest == vec[0]) lowest = (*vec.back()) + 1; 

Iterators can be used with the same clear intention as presented in the @joe_mucchiello (ed: better) answer .

Answer 6

Actually, if you make a bubble look (you know ... the one that they teach you first, and then say they will never use it again ...), you will be able to detect the first gap at an early stage of the sorting process, so you can stay there. This should give you the fastest total time.

Answer 7

OK, here are my 2 cents. Suppose you have a vector of length N.

• If N <= 2, you can directly check
• First use min_element to get the smallest element, remember it as emin
• Call nth_element to get the item in N / 2, call it ehalf
• If ehalf! = Emin + N / 2 has a space to the left, apply this method recursively there, calling nth_element on the entire array, but asking for the N / 4 element. Otherwise, repeat the procedure with the request for 3 * N / 4.

This should be a little better than sorting all the way to the front.

Answer 8

you can go with something like ....

 struct InSequence { int _current; bool insequence; InSequence() : _current(1), insequence(true){} bool operator()(int x) { insequence = insequence ? (x == _current) : false; _current++; return insequence; } }; int first_not_in_sequence(std::vector<int>& v) { std::sort(v.begin(), v.end()); return 1+std::count_if(v.begin(), v.end(),InSequence()); } 

Answer 9

Possible implementation of Thomas Cammeyer answer

I found Thomas's approach very smart and useful - as some of us dream of code, and I find the actual implementation a bit complicated, I would like to provide some ready-to-use code.

The solution presented here is as general as possible:

• Assumptions about the type of container or range are not allowed, except that their iterators must meet the requirements of ValueSwappable and RandomAccessIterator (due to partial sorting with nth_element )
• You can use any type of number - the required features are described below

Another improvement that I believe is that the condition without breaking can be checked at an early stage: since we must scan the minimum one way or another, we can also scan the maximum at the same time, and then determine if whether the range of numbers even a space is worth finding.

And last but not least, the same recursive approach can be adapted for sorted ranges! If you encode the template values ​​in the parameter whether the range is already sorted, you can simply skip the partial sorting plus make the definition of the minimum / maximum elements no-op.

 #include <type_traits> #include <iterator> #include <tuple> #include <utility> #include <algorithm> #include <cstddef> // number type must be: // * arithmetic // * subtractable (a - b) // * divisible by 2 (a / 2) // * incrementable (++a) // * less-than-comparable (a < b) // * default-constructible (A{}) // * copy-constructible // * value-constructible (A(n)) // * unsigned or number range must only contain values >0 /** Find lowest gap value in a range */ template<typename Range> typename std::remove_reference_t<Range>::value_type lowest_gap_value_unsorted(Range&& r) { static_assert(!std::is_lvalue_reference_v<Range> && !std::is_const_v<Range>, "lowest_gap_value_unsorted requires a modifiable copy of the passed range"); return lowest_gap_value_unsorted(std::begin(r), std::end(r), std::size(r)); } /** Find lowest gap value in a range with specified size */ template<typename Range> typename std::remove_reference_t<Range>::value_type lowest_gap_value_unsorted(Range&& r, std::size_t N) { static_assert(!std::is_lvalue_reference_v<Range> && !std::is_const_v<Range>, "lowest_gap_value_unsorted requires a modifiable copy of the passed range"); return lowest_gap_value_unsorted(std::begin(r), std::end(r), N); } /** Find lowest gap value in an iterator range */ template<typename Iterator> typename std::iterator_traits<Iterator>::value_type lowest_gap_value_unsorted(Iterator first, Iterator last) { return lowest_gap_value_unsorted(first, last, std::distance(first, last)); } /** Find lowest gap value in an iterator range with specified size */ template<typename Iterator> typename std::iterator_traits<Iterator>::value_type lowest_gap_value(Iterator first, Iterator last, std::size_t N) { typedef typename std::iterator_traits<Iterator>::value_type Number; if (bool empty = last == first) return increment(Number{}); Iterator minElem, maxElem; std::tie(minElem, maxElem) = std::minmax_element(first, last); if (bool contains0 = !(Number{} < *minElem)) throw std::logic_error("Number range must not contain 0"); if (bool missing1st = increment(Number{}) < *minElem) return increment(Number{}); if (bool containsNoGap = !(Number(N) < increment(*maxElem - *minElem))) return increment(*maxElem); return lowest_gap_value_unsorted_recursive(first, last, N, *minElem); } template<typename Iterator> typename std::iterator_traits<Iterator>::value_type lowest_gap_value_unsorted_recursive(Iterator first, Iterator last, std::size_t N, typename std::iterator_traits<Iterator>::value_type minValue) { typedef typename std::iterator_traits<Iterator>::value_type Number; if (N == 1) return ++minValue; if (N == 2) { // determine greater of the 2 remaining elements Number maxValue = !(minValue < *first) ? *std::next(first) : *first; if (bool gap = ++minValue < maxValue) return minValue; else return ++maxValue; } Iterator medianElem = std::next(first, N / 2); // sort partially std::nth_element(first, medianElem, last); if (bool gapInLowerHalf = (Number(N) / 2 < *medianElem - minValue)) return lowest_gap_value_unsorted_recursive(first, medianElem, N / 2, minValue); else return lowest_gap_value_unsorted_recursive(medianElem, last, N / 2 + N % 2, *medianElem); }; template<typename T> T increment(T v) { return ++v; }