Looking for the smallest missing integer in a vector containing positive and negative int?

Question

I am writing an operation to find the smallest missing element of a vector, V = 1..N + 1. This needs to be done in O (N) .

Decision:

std::vector<int> A {3,4,1,4,6,7};

int main()
{
    int max_el = *std::max_element(A.begin(), A.end()); //Find max element
    std::vector<int> V(max_el);
    std::iota(V.begin(), V.end(), 1) //Populate V with all int up to max element

    for(unsigned into i {0}; i < A.size(); i++)
    {
       int index = A[i] - 1;
       if(A[i] == V[index]) //Search V in O(1)
       {
         V[index] = max_el; //Set each to max_el, leaving the missing int 
       }
    }
    return *std::min_element(V.begin(), V.end()); //Find missing int as its the lowest (hasn't been set to max_el)
}

//Output: 2

This works great.

However, now I'm trying to get this to work with a vector containing negative ints.

Solution two:

My logic is to use the same approach, however the “weight” of the indices sets the size of the vector and the number of negative ints in the vector:

std::vector<int> A {-1, -4, -2, 0, 3, 2, 1}
int main()
{
   int max_el = *std::max_element(A.begin(), A.end());
   int min_el = *std::min_element(A.begin(), A.end());
   int min_el_abs = abs(min_el); //Convert min element to absolute
   int total = min_el_abs + max_el;

   std::vector<int> V(total + 1);
   std::iota(V.begin(), V.end(), min_el);
   int index;

   //Find amount of negative int's
   int first_pos;
   for(unsigned int i {0}; i < A.size(); i++)
   {
      if(A[i] >= 0) {first_pos = i; break;}
   }

   for(unsigned int i {0}; i < A.size(); i++)
   {
      if(A[i] <= 0) //If negative
      {
          index = (A.size() - first_pos) - abs(A[i]);
       } else 
       {
          index = (A[i] + 1) + first_pos;
       }
       if(A[i] == V[index])
       {
          V[index] = 0;
       }
    } 
    return *std::min_element(V.begin(), V.end());
 } 

 //Output: -3

Solution Two do not compare the values ​​of two vectors (A and V), since the calculation indexusing the indicated methods with a positive int does not work.

1) How can I get my solution 2 to work with an unordered vector of negative ints?

2) 2 , int?

Answer 1

, :

int main()
{
  std::vector<int> A {-3, -1, 0, 1, 3, 4};
  auto relative_pos = std::minmax_elment(A.begin(), A.end());
  std::vector<bool> Litmus( *(relative_pos.second) - *(relative_pos.first), false); //Create vector of size max val - min val)

  auto lowest_val = *(relative_pos.first);
  for(auto x : A)
  {
     Litmus[i - lowest_val] = true;
  }
  auto pos = std::find(Litmus.begin(), Litmus.end(), false); //Find the first occurring false value
  std::cout<< (pos - Litmus.begin()) + lower<<std::endl; //Print the val in A relative to false value in Litmus
}

.

Answer 2

O (max (N, M)), N A M - V ( max (A _i)), ( std::min_element, std::max_element, for, V std::iota ).

, ( ; into int), ... main(), .

[ 1, A], , [min (A _i), max (A _i)], .

L.Senioins, , .

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

template <class ForwardIt>
typename std::iterator_traits<ForwardIt>::value_type
lowest_missing(ForwardIt first, ForwardIt last)
{
    if ( first == last )
        throw std::string {"The range is empty"};
    // find both min and max element with one function
    auto result = std::minmax_element(first, last);

    // range is always > 0  
    auto range = *result.second - *result.first + 1;
    if ( range < 2 )
        throw std::string {"Min equals max, so there are no missing elements"};
    std::vector<bool> vb(range); // the initial value of all elements is false

    for (auto i = first; i != last; ++i)
        vb[*i - *result.first] = true;

    // search the first false
    auto pos = std::find(vb.cbegin(), vb.cend(), false);
    if ( pos == vb.cend() )  // all the elements are true
        throw std::string {"There are no missing elements"};

    return std::distance(vb.cbegin(), pos) + *result.first;
}

template <class ForwardIt>
void show_the_first_missing_element(ForwardIt first, ForwardIt last)
{
    try
    {
        std::cout << lowest_missing(first, last) << '\n';
    }
    catch(const std::string &msg)
    {
        std::cout << msg << '\n';
    }
}

int main() {
    std::vector<int> a { 1, 8, 9, 6, 2, 5, 3, 0 };
    show_the_first_missing_element(a.cbegin(), a.cend());

    std::vector<int> b { -1, -4, 8, 1, -3, -2, 10, 0 };
    show_the_first_missing_element(b.cbegin(), b.cend());
    show_the_first_missing_element(b.cbegin() + b.size() / 2, b.cend());

    std::vector<int> c { -2, -1, 0, 1, 2, 3 };
    show_the_first_missing_element(c.cbegin(), c.cend());

    std::vector<int> d { 3, 3, 3 };
    show_the_first_missing_element(d.cbegin(), d.cend());

    std::vector<int> e;
    show_the_first_missing_element(e.cbegin(), e.cend());

    return 0;
}

, :

4
2
-1
There are no missing elements
Min equals max, so there are no missing elements
The range is empty

Answer 3

My solution is to make a vector bool(or charjust to prevent compilation warnings about casting up bool) that has the size of all possible elements. All elements are initialized to 0, and then assigned 1, which indicates the absence of an element. All you have to do is find the index of the first element 0, which is the lowest missing element.

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> A{ -1, 0, 11, 1, 10, -5 };

int main() {
    if (A.size() > 1) {
        int max_el = *std::max_element(A.begin(), A.end());
        int min_el = *std::min_element(A.begin(), A.end());
        int range = abs(max_el - min_el) + 1;

        std::vector<int> V(range, 0);

        for (size_t i = 0; i < A.size(); i++)
            V[A[i] - min_el] = 1;

        if (*std::min_element(V.begin(), V.end()) == 0)
            std::cout << std::distance(V.begin(), std::find(V.begin(), V.end(), 0)) + min_el;
        else
            std::cout << "There are no missing elements" << std::endl;
    }
    else
        std::cout << "There are no missing elements" << std::endl;

    std::cin.get();
}

Answer 4

#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
int solution(vector<int> &A) {
    std::vector<int>::iterator it = std::max_element(A.begin(),A.end()); 
    try
    {
        sort(A.begin(),A.end());    
        std::vector<int>::iterator it = std::unique(A.begin(),A.end());
        A.resize(std::distance(A.begin(),it));

        for(int i = 0, j = 1; i < A.size(); i++)
        {
            if( A[i] != j)          
            {
                return j;
            }           
            j++;
        }

    }
    catch(exception &e)
    {
        std::cout<<e.what()<<std::endl;
    }
    return ++(*it);
}