---

0660. 移除 9

• 标签：数学
• 难度：困难

题目链接

• 0660. 移除 9 - 力扣

题目大意

描述：

从 $1$ 开始，移除包含数字 $9$ 的所有整数，例如 $9$，$19$，$29$，……

这样就获得了一个新的整数数列：$1$，$2$，$3$，$4$，$5$，$6$，$7$，$8$，$10$，$11$，……

给定一个整数 $n$。

要求：

返回新数列中第 $n$ 个数字（下标从 $1$ 开始）。

说明：

• $1 \le n \le 8 \times 10^8$。

示例：

• 示例 1：

输入：n = 9
输出：10

• 示例 2：

输入：n = 10
输出：11

解题思路

思路 1：进制转换

思路 1：算法描述

移除所有包含数字 $9$ 的整数后，剩余的数字序列实际上是一个九进制数系统。

核心思路：

• 原始序列：$1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ...$（跳过所有包含 $9$ 的数字）
• 这相当于九进制：$1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ...$
• 第 $n$ 个数字就是 $n$ 的九进制表示。

算法步骤：

1. 将 $n$ 转换为九进制。
2. 返回转换后的结果。

思路 1：代码

class Solution:
    def newInteger(self, n: int) -> int:
        # 将 n 转换为九进制
        result = 0
        base = 1
        
        while n > 0:
            result += (n % 9) * base
            n //= 9
            base *= 10
        
        return result

思路 1：复杂度分析

• 时间复杂度：$O(\log n)$，需要将 $n$ 转换为九进制。
• 空间复杂度：$O(1)$，只使用了常数额外空间。