C++ find first non repeating integer in an array with O(n) space

Question

I would like to return first (first met, from left to right) non repeating element in an array.

i come with an algorithm that return smallest integer that is non repeating in an array quite easily, using only a array as extra space with length the max integer value in the array:

// smallest non repeating integer

int firstNonRepeatingInteger(int* input, int n)
{

     max = std::numeric_limits<int>::min() ;

     for(int i = 0 ; i < n ; i++)
     {
        if(input[i] > max)  
            max = input[i];
     }

     int* count = new int[max];

     for(int i = 0 ; i < n ; i++)
          count[input[i]] += 1 ;

     int j = 0;
     while(count[i] != 1)
       j++ ; 

     if(j < n)
        return input[count[j]] ;
     else
        return -1 ;

}

however, i cannot find an algorithm to find the first met, except having another n-array storing the time an integer is encountered.

any idea ? any other implementation of first algorithm?

thanks

Something like std::find_if_not and comparing with the first element would work. — Qaz
– Qaz, Commented Oct 7, 2012 at 18:31
Are you happy to loop through the array again? If so then just return input[i] the first time count[input[i]]==1 — Peter de Rivaz
– Peter de Rivaz, Commented Oct 7, 2012 at 18:37
Going with the find_if_not, if you can use it, here's a sample. — Qaz
– Qaz, Commented Oct 7, 2012 at 19:11

Stacker · Accepted Answer · 2012-10-07 20:36:19Z

4

You almost had it:

#include <limits>
#include <iostream>

int firstNonRepeatingInteger(int* input, int n)
{
  int min = std::numeric_limits<int>::max() ;
  int max = std::numeric_limits<int>::min() ;

  // Find min/max values in input array.
  for(int i = 0; i < n; ++i)
  {
    if (input[i] > max)
      max = input[i];
    if (input[i] < min)
      min = input[i];
  }

  int* count;
  if (max - min + 1 > n)
  {
    count = new int[max - min + 1];
    // count has more elements than input, so only initialize
    // those elements which will be used.
    for(int i = 0; i < n; ++i)
      count[input[i] - min] = 0;
  }
  else
  {
    // Just initialize everything which is more efficient if
    // count has less elements than input.
    count = new int[max - min + 1]();
  }

  // Count number of occurrences.
  for(int i = 0; i < n; ++i)
    ++count[input[i] - min];

  // Find first non repeating element and return its index,
  // or -1 if there is none.
  int index = -1;
  for (int i = 0; i < n; ++i)
  {
    if (count[input[i] - min] == 1)
    {
      index = i;
      break;
    }
  }
  delete[] count;
  return index;
}

int main()
{
  int values[5] = {-2, 4, 6, 4, -2};
  int index = firstNonRepeatingInteger(values, 5);
  if (index >= 0)
  {
    std::cout << "Found first non repeating integer " << values[index] <<
      " at index " << index << "." << std::endl;
  }
  else
    std::cout << "Found no non repeating integer in array." << std::endl;
  return 0;
}

Note that your code had several issues:

You never deleted the allocated memory.
new int[max] does not initialize the array with zeros. You need to use new int[max]() instead. Note the empty parentheses which will set all elements to zero (see ISO C++03 5.3.4[expr.new]/15).
Negative values in the input array will result in memory access violations.

edited Oct 7, 2012 at 20:36

answered Oct 7, 2012 at 19:45

Stacker

1,23016 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Vaughn Cato Over a year ago

Note: If n is the size of the array, then the algorithm is not O(n). It is O(n+k) where k is the size of the range of integers.

Stacker Over a year ago

Well ok if min and max are far off each other you may change initialization of the count array with int* count = new int[max - min + 1]; for(int i = 0; i < n; ++i) count[input[i] - min] = 0; Depends on the input if this is more efficient or not.

kiriloff Over a year ago

@Stacker thanks thats it, i oversaw that you have to retrieve the first met simply iterating on input instead of count.

Collectives™ on Stack Overflow

C++ find first non repeating integer in an array with O(n) space

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related