title: C++ find first non repeating integer in an array with O(n) space
body: <p>I would like to return first (first met, from left to right) non repeating element in an array. </p>
  
  <p>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:</p>
  
  <pre><code>// smallest non repeating integer
  
  int firstNonRepeatingInteger(int* input, int n)
  {
  
       max = std::numeric_limits&lt;int&gt;::min() ;
  
       for(int i = 0 ; i &lt; n ; i++)
       {
          if(input[i] &gt; max)  
              max = input[i];
       }
  
       int* count = new int[max];
  
       for(int i = 0 ; i &lt; n ; i++)
            count[input[i]] += 1 ;
  
       int j = 0;
       while(count[i] != 1)
         j++ ; 
  
       if(j &lt; n)
          return input[count[j]] ;
       else
          return -1 ;
  
  }
  </code></pre>
  
  <p>however, i cannot find an algorithm to find the first met, except having another n-array storing the time an integer is encountered. </p>
  
  <p>any idea ? any other implementation of first algorithm?</p>
  
  <p>thanks</p>