文章目录

• 题目
• • 标题和出处
  • 难度
  • 题目描述
  • • 要求
    • 示例
    • 数据范围
• 解法
• • 思路和算法
  • 代码
  • 复杂度分析

题目

标题和出处

标题：整数转罗马数字

出处：12. 整数转罗马数字

难度

3 级

题目描述

要求

罗马数字包含以下七种字符：I\texttt{I}I、V\texttt{V}V、X\texttt{X}X、L\texttt{L}L、C\texttt{C}C、D\texttt{D}D 和 M\texttt{M}M。

例如，罗马数字 2\texttt{2}2 写做 II\texttt{II}II，即为两个 1\texttt{1}1 相加。12\texttt{12}12 写做 XII\texttt{XII}XII，即为 X+II\texttt{X + II}X + II。27\texttt{27}27 写做 XXVII\texttt{XXVII}XXVII，即为 XX+V+II\texttt{XX + V + II}XX + V + II。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4\texttt{4}4 不写做 IIII\texttt{IIII}IIII，而是 IV\texttt{IV}IV，即数字 1\texttt{1}1 在数字 5\texttt{5}5 的左边，所表示的数等于 5\texttt{5}5 减 1\texttt{1}1 得到的数值 4\texttt{4}4。同样地，数字 9\texttt{9}9 表示为 IX\texttt{IX}IX。这个特殊的规则只适用于以下六种情况：

• I\texttt{I}I 可以放在 V\texttt{V}V（5\texttt{5}5）和 X\texttt{X}X（10\texttt{10}10）的左边，来表示 4\texttt{4}4 和 9\texttt{9}9。
• X\texttt{X}X 可以放在 L\texttt{L}L（50\texttt{50}50）和 C\texttt{C}C（100\texttt{100}100）的左边，来表示 40\texttt{40}40 和 90\texttt{90}90。
• C\texttt{C}C 可以放在 D\texttt{D}D（500\texttt{500}500）和 M\texttt{M}M（1000\texttt{1000}1000）的左边，来表示 400\texttt{400}400 和 900\texttt{900}900。

给你一个整数，将其转换成罗马数字。

示例

示例 1：

输入：num=3\texttt{num = 3}num = 3
输出："III"\texttt{"III"}"III"

示例 2：

输入：num=4\texttt{num = 4}num = 4
输出："IV"\texttt{"IV"}"IV"

示例 3：

输入：num=9\texttt{num = 9}num = 9
输出："IX"\texttt{"IX"}"IX"

示例 4：

输入：num=58\texttt{num = 58}num = 58
输出："LVIII"\texttt{"LVIII"}"LVIII"
解释：L=50\texttt{L = 50}L = 50，V=5\texttt{V = 5}V = 5，III=3\texttt{III = 3}III = 3。

示例 5：

输入：num=1994\texttt{num = 1994}num = 1994
输出："MCMXCIV"\texttt{"MCMXCIV"}"MCMXCIV"
解释：M=1000\texttt{M = 1000}M = 1000，CM=900\texttt{CM = 900}CM = 900，XC=90\texttt{XC = 90}XC = 90，IV=4\texttt{IV = 4}IV = 4。

数据范围

• 1≤num≤3999\texttt{1} \le \texttt{num} \le \texttt{3999}1≤num≤3999

解法

思路和算法

为了将整数转换成罗马数字，需要从高到低遍历整数的每一位并转换成对应的罗马数字中的符号。

整数的每一位都是 000 到 999，只需要考虑大于 000 的数位。数位值 111 和 555 都可以用一个字符表示，数位值 222、333、666、777 和 888 都可以用两个至四个字符的加法表示，数位值 444 和 999 都可以用两个字符的减法表示。

对于一个字符表示和多个字符的加法表示，由于每个字符的值不会大于当前数位的值，因此可以直接转换。对于减法表示，由于存在字符的值大于当前数位的值（444 的表示为 5−15 - 15−1，999 的表示为 10−110 - 110−1），因此不能直接转换，而是需要引入新的符号。

罗马数字包含 777 种字符，罗马数字中的减法规则定义了 666 种复合符号，因此共有 131313 种符号。

使用上述 131313 种符号，整数中每个数位的每个值对应的罗马数字的表示是唯一的，因此每个整数对应的罗马数字的表示是唯一的。

转换方法是：从大到小依次遍历 131313 种符号对应的数值，对于每个数值，如果当前的 num\textit{num}num 大于或等于该数值，则将当前符号拼接到罗马数字中，并将当前数值从 num\textit{num}num 中减去，直到 num\textit{num}num 小于当前数值，然后对下一个数值继续上述操作，直到 num\textit{num}num 变成 000。

上述转换方法的一种等价做法是：对于每个数值，计算当前的 num\textit{num}num 除以该数值的商（向零取整），即可得到当前符号在罗马数字中的出现次数，将当前符号按照出现次数拼接到罗马数字中，并将 num\textit{num}num 对当前的数值取模，即完成当前符号的拼接，然后对下一个数值继续上述操作，直到 num\textit{num}num 变成 000。

代码

class Solution {static final int[] VALUES = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};static final String[] SYMBOLS = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};public String intToRoman(int num) {StringBuffer sb = new StringBuffer();int length = VALUES.length;for (int i = 0; i < length; i++) {int value = VALUES[i];String symbol = SYMBOLS[i];int count = num / value;for (int j = 0; j < count; j++) {sb.append(symbol);}num %= value;}return sb.toString();}
}

复杂度分析

• 时间复杂度：O(1)O(1)O(1)。由于符号的数量固定，因此转换的操作次数固定。

• 空间复杂度：O(1)O(1)O(1)。由于符号的数量固定，因此存储对应关系使用的空间固定。