特殊字符串序列第k位查询的最小时间复杂度问题咨询

问题答案 #

核心结论 #

• 最小时间复杂度为 O(n)，若采用迭代实现可达到 O(1) 额外空间复杂度
• 不需要生成任何前序序列元素即可完成查询

推导过程 #

1. 序列长度规律

根据构造规则可推出 Sₙ 的长度公式：
len(Sₙ) = 2ⁿ - 1
验证：len(S₁)=1=2¹-1，len(S₂)=3=2²-1，len(S₃)=7=2³-1，完全匹配已知样例。

2. 位查询逻辑

Sₙ 由 Sₙ₋₁ + "0" + Sₙ₋₁ 拼接而成，所以 Sₙ 的中间位置为 2ⁿ⁻¹，只需按以下规则逐层缩小查询范围即可：

• 若查询位置 k == 2ⁿ⁻¹：直接返回字符 0
• 若 k < 2ⁿ⁻¹：当前位等价于 Sₙ₋₁ 的第 k 位，将n减1后重复判断
• 若 k > 2ⁿ⁻¹：当前位等价于 Sₙ₋₁ 的第 k - 2ⁿ⁻¹ 位，将n减1、k更新为 k - 2ⁿ⁻¹ 后重复判断
• 当n缩小到1时，直接返回字符 1

整个过程只需要做数值比较和运算，不需要生成任何字符串，也不需要存储前序序列的内容。

3. 复杂度验证

每次判断都会将n的值减1，最多执行n次运算，所以时间复杂度为 O(n)；如果用迭代代替递归实现，可以避免栈空间开销，额外空间复杂度为 O(1)。

内容的提问来源于stack exchange，提问作者StrugglingCollegeStudent