c++ - 第一次出现的非重复数字

Question

假设您有一个数字 vector ，例如:0,4,2,3,1,0,6,4

找出这个列表中第一个没有重复的数字。所以为了举例，答案是 2。假设:

• 您可以修改提供的载体
• 如果找不到任何东西返回-1
• 提供的数字在 0 - 10,000 之间

我提供了两个我想到的答案，我认为名为 ArraySolution 的函数是最好的，但是任何人都可以想到更快的东西并解释一下:)

谢谢

#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 是 O(N log(N)) 因为有 N 个插入 O(logN) -- 大小也是 O(NlogN)

ArraySolution 似乎是 O(N^2)，因为 N 的某个分数有 N 个循环 - 但 K 可能不错

以下是 O(N)，大小为 O(1)，因为查找是固定的:

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

它利用了输入范围仅为 10000 的事实，因此有 N 个插入是 O(1) 的:

•提供的数字介于 0 - 10,000 之间

编辑:如评论中所述(我的版本)，对于大输入 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;
}