查找字符串中不存在的最小子字符串

Question

我有一个只包含数字0-9的字符串.字符串的长度可以在1到1,000,000个字符之间.我需要在线性时间内找到字符串中不存在的最小数字.这里有些例子:

1023456789       //Smallest number not in string is 11
1023479          //Smallest number not in string is 5
112131405678910  //Smallest number not in string is 15

大小为1,000,000,我认为字符串中不存在的最小数字必须至多为6位数.

我的方法是生成所有数字0到999,999并将它们全部插入到一个向量中(按顺序).然后制作一个标记已经看到的字符串的地图.然后我遍历字符串,对于每个位置,我得到从它开始的所有子字符串,大小为1到6,并且我在地图中将所有这些子字符串标记为true.最后,我只是逐个检查所有键,当我发现第一个在地图中有假值时,我打印出来.

以下是一些代码段:

string tmp="0";
string numbers[999999];

void increase(int pos)
{
    if(pos==-1)tmp.insert(0,"1");
    else if(tmp.at(pos)!='9')tmp.at(pos)++;
    else
    {
        tmp.at(pos)='0';
        increase(pos-1);
    }
}

//And later inside main
for(int j=0;j<999999;j++)
{
    numbers[j]=tmp;
    increase(tmp.size()-1);
}

---

for(int j=0;j<input.size();j++)
    {
        for(int k=0;k<6;k++)
        {
            string temp="";
            if(j+k<input.size())
            {
                temp+=input.at(j+k);
                appeared[temp]=true;
            }
        }
    }

---

int counter=0;
while(appeared[numbers[counter]])counter++;
cout<<numbers[counter]<<endl;

关于算法第一部分的说明.我生成一次矢量,然后我用它100个字符串.我需要在不到4秒的时间内解析所有100个字符串.

这个算法对我来说太慢了,因为它是目前的.我可以优化一些代码,还是应该考虑不同的方法？

Answer 1

由于您只需要知道某个数字是否已被看到，因此使用 astd::vector<bool>来存储该指示可能是最简单的。当您遍历输入数字时，您在数组中将数字标记为 true。完成后，您将遍历数组，并打印出第一个仍为 false 的项目的索引。