求第N个至少含一位偶数数字的数：大N场景下枚举超时的程序优化

原暴力枚举法的核心问题是需要逐个数遍历判断，当N达到10^18量级时，遍历次数和N规模同量级，根本无法在1秒内完成计算。可以通过补集思想+二分查找的思路把时间复杂度压到O(位数 * logN)，哪怕N是1e18也能瞬间返回结果。

核心逻辑转换 #

我们要找的“至少含一个偶数数位的自然数”，和“所有数位全为奇数的自然数”是完全互补的集合：

• 对任意正整数x，1~x范围内的正整数总数是x个
• 记f(x)为1~x范围内，所有数位全为奇数的数的数量（这类数不符合题目要求，因为没有任何偶数数位）
• 那么1~x范围内符合题目要求的数的总数就是 g(x) = x - f(x)

g(x)是严格单调递增的函数：x每增加1，只要x+1不是全奇的数，g(x)就会加1；如果x+1是全奇的数，g(x)保持不变。我们要找的第N个符合要求的数，就是满足g(x) = N的最小x。

f(x)的快速计算方法 #

f(x)本质上是统计x以内，每一位数字都只能是1、3、5、7、9的数的总数，完全可以在O(x的位数)时间内算完：

1. 先把x转成数字列表，统计所有长度比x短的全奇数总数：长度为k的全奇数，每一位有5种选择（1/3/5/7/9），所以长度1到k-1的总数是 5 + 5^2 + ... +5^(k-1)
2. 从最高位开始逐位遍历：
   • 计算当前位上，比当前数字小的奇数有多少个，记为cnt
   • 每一个这样的奇数，作为当前位数字时，后面的所有低位都可以任意选5个奇数字，贡献的数量是 cnt * 5^(剩余低位数量)
   • 如果当前位的数字本身是偶数，说明不可能用这个位组成全奇数的数，直接跳出循环，不用遍历更低的位
   • 如果当前位的数字本身是奇数，就继续遍历下一位
   • 如果顺利遍历完所有位，说明x本身就是全奇数的数，最后要给f(x)加1

举个实际计算的例子，x=24：

• x是2位数，短于2位的全奇数总数是5个（1,3,5,7,9）
• 最高位是2，比2小的奇数只有1个，剩余1位，贡献 1*5^1=5 个（11,13,15,17,19）
• 最高位数字2是偶数，直接跳出循环
• 最终f(24)=5+5=10，g(24)=24-10=14，刚好对应N=14时的结果24，和示例完全匹配

二分查找的实现 #

因为g(x)是单调递增的，我们不需要逐个枚举x，只要通过二分查找定位满足g(x)=N的x即可：

• 查找下界直接取N：因为哪怕全奇数的数量为0，x=N也是目标值
• 查找上界取2N：全奇数的数量在1e18范围内仅为~5e12，远小于N的规模，2N的上界完全足够覆盖目标值
• 整个二分过程最多需要log2(2*1e18)≈61次迭代，每次迭代计算f(x)仅需18步左右，总共的运算量不到1000次，哪怕N是1e18也能瞬间出结果

参考代码（Python 实现） #

def count_all_odd(x):
    s = list(map(int, str(x)))
    length = len(s)
    total = 0
    # 先算所有比当前位数短的全奇数
    for k in range(1, length):
        total += 5 ** k
    # 逐位算当前位的贡献
    for i in range(length):
        current = s[i]
        # 计算当前位上小于current的正奇数数量
        cnt = current // 2
        remain = length - i -1
        total += cnt * (5 ** remain)
        # 当前位是偶数，后续无法组成全奇数，直接跳出
        if current % 2 == 0:
            break
    else:
        # 循环完整走完，说明x本身是全奇数，补加1
        total +=1
    return total

def find_nth(N):
    left = N
    right = 2 * N
    while left < right:
        mid = (left + right) //2
        g_mid = mid - count_all_odd(mid)
        if g_mid >= N:
            right = mid
        else:
            left = mid +1
    return left

# 测试示例
print(find_nth(1))  # 输出2
print(find_nth(5))  # 输出10
print(find_nth(9))  # 输出18
print(find_nth(14)) # 输出24

性能说明 #

哪怕N取接近1e18的值，整个算法的运算量也不到1000次基本计算，完全满足1秒内返回结果的要求，和原来逐次枚举的方法比，性能提升了十几个数量级。

内容的提问来源于stack exchange，提问作者Nodirbek O'ktamov