如何无需构造完整序列求2/5/7组成的递增数字序列指定元素后继

核心思路 #

这个问题完全不需要提前构造完整序列，本质是自定义进位规则的加1运算，类比十进制加1的逻辑，仅需逐位处理输入数字即可，时间复杂度仅和输入数字的位数相关，效率极高。
序列的可用数字只有3个，从小到大顺序为2 < 5 < 7，我们只需要按照这个规则处理进位即可。

具体步骤 #

• 先把输入的数字转为字符列表，方便逐位修改，从最后一位（最低位）开始遍历
• 每一位的处理规则：
  • 若当前位是2：替换为5，终止遍历，直接拼接列表为数字返回
  • 若当前位是5：替换为7，终止遍历，直接拼接列表为数字返回
  • 若当前位是7：替换为2，继续向前遍历高位处理进位
• 若所有位都遍历完成仍未终止（说明输入全由7组成，比如7、77、777等），在列表最前面插入字符2，再拼接返回即可

示例验证 #

1. 示例输入277755：最后一位是5，替换为7，直接得到277757，符合预期
2. 输入27：最后一位是7→改为2，前一位是2→改为5，得到52
3. 输入777：所有位都是7，全部改为2后前面加2，得到2222

代码实现（Python） #

def find_next_valid_num(n):
    digits = list(str(n))
    i = len(digits) - 1
    while i >= 0:
        if digits[i] == '2':
            digits[i] = '5'
            break
        elif digits[i] == '5':
            digits[i] = '7'
            break
        else: # 当前位为7，触发进位
            digits[i] = '2'
            i -= 1
    # 所有位都完成进位，说明原数全是7
    if i < 0:
        digits.insert(0, '2')
    return int(''.join(digits))

该方案时间复杂度为O(k)，k是输入数字的位数，空间复杂度为O(k)，完全不需要存储额外的序列元素，哪怕输入是上百位的超长数字也能毫秒级返回结果。

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