First occurring non-repeating number

Question

Assume you have a vector of numbers for example: 0,4,2,3,1,0,6,4

Find the first number in this list that is not repeated. So for the examples sake the answer is 2. Assumptions:

• You can modify the vector provided
• If you cant find anything return -1
• Numbers provided are between 0 - 10,000

I have provided two answers that I have thought of, and I think the function called ArraySolution is the best, however can anybody think of something that is faster and explain :)

Thanks

#include <iostream>
#include <vector>
#include <time.h>
#include <map>

void FillVectorRandomly(std::vector<int>& numbers, int size, int lowerRange, int higherRange)
{
        if(size == 0)
                return;
        if(lowerRange < 0)
                return;
        if(higherRange < lowerRange)
        {
                int temp = lowerRange;
                lowerRange = higherRange;
                higherRange = temp;
        }

        srand(time(NULL));
        int dif = higherRange - lowerRange+1;

        for(int i = 0; i < size; ++i)
                numbers.push_back((rand() % dif) + lowerRange);
}

int MapSolution(std::vector<int>& numbers)
{
        std::map<int, int> mapNumbers;

        for(int i = 0; i < numbers.size(); ++i)
        {
                mapNumbers[numbers[i]] = mapNumbers[numbers[i]] + 1;
        }

        for(int i = 0; i < numbers.size(); ++i)
        {
                if(mapNumbers[numbers[i]] == 1)
                        return numbers[i];
        }
        return -1;
}

int ArraySolution(std::vector<int>& numbers)
{
        for(int i = 0; i < numbers.size(); ++i)
        {

                if(numbers[i] != -1)
                {
                        int count = 0;
                        for(int j = i+1; j < numbers.size(); ++j)
                        {
                                if(numbers[j] == numbers[i])
                                {
                                        numbers[j] = -1;
                                        count++;
                                }
                        }
                        if(count == 0)
                                return numbers[i];
                }
                numbers[i] = -1;
        }
}
int main()
{
        std::vector<int> numbers;
        FillVectorRandomly(numbers, 4, 0, 5);
        int m = MapSolution(numbers);
        int a = ArraySolution(numbers);
        return 0;
}

Answer 1

MapSolution is O(N log(N)) since there are N inserts O(logN) -- also Size is O(NlogN)

ArraySolution seems to be O(N^2) since there are N loopsof some fraction of N - but K might be good

The following is O(N) with size O(1) since the lookup is fixed:

int lookup_solution(std::vector<int>& numbers)
{
        int lookup[10000+1] = {};
        for (int i=0; i<numbers.size(); ++i)
        {
                lookup[numbers[i]]++;
        }
        for (int i=0; i<numbers.size(); ++i)
        {
                if (lookup[numbers[i]] == 1)
                {
                        return numbers[i];
                }
        }

        return -1;
}

It takes advantage of the fact that the input range is only 10000 and so there are N inserts that are O(1) :

•Numbers provided are between 0 - 10,000

EDIT: As noted in comments (my version), for a large input vector:

int lookup_solution(std::vector<int>& numbers)
{
        static const int max_value=10000;
        int count[max_value+1] = {};  // counts occurrences of index 
        int order[max_value+1];       // keeps order of values seen 
        int index[max_value+1];       // index into order for where order is found
        int order_index=0;

        for (int i=0; i<numbers.size(); ++i)
        {
                int n=numbers[i];
                int seen=count[n];
                if (seen == 0)             // first time
                {                        
                    count[n]=1;
                    order[order_index]=n;
                    index[n]=order_index;
                    order_index++;
                }
                else if (seen == 1)      // not eligible (-1)
                {                       
                    count[n]=-1;         // use -1 since it might be in a register
                    order[index[n]]=-1; 
                } // else do nothing
        }
        for (int i = 0; i < order_index; ++i)
        {
             if (order[i] != -1)
             {
                   return order[i];
             }
        }   
        return -1;
}