找到不作为字符串子序列出现的最小数字

Question

来自SPSEJ上的STRSEQ:

给定一串数字,找到在给定字符串中不出现的最小非负整数作为子序列.

我尝试了一种方法,我逐步从0中找到数字.但我的方法是O(answer?*?length?of?the?string).O(length?of?string)这个问题有办法吗？

例子:

输入

• 9876543210
• 21698921085321984125
• 12345678901

产量

• 11
• 7
• 22

Answer 1

此算法所需的数据结构:

• bitset数组,每个输入字符串元素一个bitset(最后一个空位集),每位一位(每个bitset的大小为10)
• 10堆位置 - 每个数字(可选)
• 计数器(计算答案中的数字)

算法:

1. 向后扫描输入字符串,将当前位置推送到与该位置的数字对应的堆栈,从先前位置复制位集,并在当前位置设置与数字对应的位.当当前bitset中的所有位都置1时,递增计数器并清除bitset.
2. 如果计数器仍为零,则获取当前位集中的最低有效位,并使用与该位对应的单个数字来构造结果数.
3. 如果唯一的未设置位是"零",则将得到的数字构造为"10",然后是步骤4的结果(其中初始数字"0"是预先确定的).
4. 获取当前位集中的最低有效位(但是当第一次执行此步骤时,忽略对应于"0"的位),将其用作结果的下一位,弹出与该位对应的堆栈(直到获得位置不小于当前位置),并将当前位置设置为该堆栈的索引加1.获取与当前位置对应的bitset并重复步骤4.此步骤应执行"counter + 1"次或直到尝试弹出空堆栈.

替代算法:

另一种方法是将大多数计算从步骤4移到步骤1.在这种情况下,我们需要更简单的数据结构,而不是bitset数组和10个堆栈.

解释和示例:

该算法的步骤1确定包含任何单位数作为子序列的最短后缀.然后它找到与此后缀相邻的最短子字符串,该子字符串也包含任何一位数字.它们一起提供包含任意两位数字的最短后缀.对于3位,4位后缀等继续该过程.此预处理步骤确定哪些数字可以写在这些n位数字的左侧,以便相应的子序列存在于输入字符串的某些后缀中. (此信息包含在位集中).

例如,对于输入字符串,12345678901此步骤确定从索引"1"开始的后缀包含任何可能的单位数字.它还以下列方式填充位集:

index: bitset:
10     0000000010
9      0000000011
8      1000000011
7      1100000011
6      1110000011
5      1111000011
4      1111100011
3      1111110011
2      1111111011
1      0000000000
0      0000000010

步骤2,3处理一些极端情况.

步骤4从检查位置"0"的位集开始,找到最小可能的起始位.在我们的示例中,位"1"被设置,这意味着我们无法用"1"开始我们的2位数字(所有这些数字都已经在字符串中).我们也不能用"0"开始它.下一个未设置位为"2",因此我们将以"2"开始数字.

我们可以使用相应的堆栈或者只是顺序搜索字符串以到达第一个数字"2"的位置.我们号码的剩余数字应该在数字"2"后面的后缀中.此后缀起始位置的位集为"1111111011",表示此后缀中唯一未使用的数字为"2".我们应该在这里停下来,因为"counter + 1"是2,我们只用了第2步的2次迭代.所以答案是"22".

这是其他具有较差时间复杂度的算法O(answer + length of the string).

对于每个数字(从0到9)准备一个索引数组,其中每个索引指向给定位置或右侧的最接近数字的出现.例如:

For string     216989210...
and digit "1": 11777777...

这可以通过向后扫描输入数组来实现,并且一旦我们看到适当的数字,就开始将其索引写入索引数组.对于上面的示例,这意味着我们在位置7处看到最右边的数字"1"并且用7填充索引数组,直到我们在索引1处看到另一个数字"1"出现.然后我们用该索引填充剩余的位置.

现在,我们可以很容易地减少从OP提到的算法的复杂性O(answer * length of the string)来O(answer + length of the string).只需按照其中一个索引数组提供的链接,即可获得当前数字中下一个数字的最近位置.

例如,我们可以尝试前61个非负数,然后对于数字"61",我们在第一个位置检查索引数组"6"以找到索引"2"(这不是必需的,因为已找到此索引在处理"60"时,我们在下一个位置(2 + 1)检查索引数组"1"以找到索引"7".这意味着"61"出现在给定的字符串中,我们可以继续"62"......