First occurring non-repeating number

c++

Solution

`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;
}

Problem

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; } ```

Original source