力扣-12. 整数转罗马数字（Integer to Roman）

最后编辑于2025-06-13

12. 整数转罗马数字（Integer to Roman）

Medium

罗马数字由七个符号表示：I(1), V(5), X(10), L(50), C(100), D(500), M(1000)。

在通常书写中，较大的数字放在左边，特殊情况使用减法表示（例如 IV 表示 4，IX 表示 9，XL 表示 40，XC 表示 90，CD 表示 400，CM 表示 900）。给定一个整数，将其转为罗马数字（1 到 3999 之间）。

示例：

  • 输入：3，输出："III"
  • 输入：4，输出："IV"
  • 输入：9，输出："IX"
  • 输入：58，输出："LVIII"（L = 50, V = 5, III = 3）
  • 输入：1994，输出："MCMXCIV"（M = 1000, CM = 900, XC = 90, IV = 4）

约束：

  • 1 <= num <= 3999

思路与解法

由于输入范围限定在 1 到 3999，使得问题容易化为按位处理（千位、百位、十位、个位）。常见实现方式有三类：

  1. 位分解 + 按位处理：分别提取千/百/十/个位，对于每一位按其取值范围映射到对应的罗马表示（例如 4 -> IV，9 -> IX，5-8 -> V + I…）。代码实现按位处理即可。

  2. 贪心查表：预先准备从大到小的数值与对应罗马字符串列表（如 1000->”M”, 900->”CM”, …），然后贪心地从大到小不断减去当前能匹配的值并拼接对应字符串，直到 num 为 0。

  3. 按位查表（常数时间）：直接为千/百/十/个位分别构造长度有限的小表，按下标拼接四段字符串，代码简洁且 O(1) 时间。

下面给出三种 C++ 实现示例。

方法一：位分解 + 映射处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string intToRoman(int num) {
        string res = "";
        vector<char> roman{'M','D','C','L','X','V','I'};
        vector<int> value{1000,500,100,50,10,5,1};
        for (int n = 0; n < 7; n += 2) {
            int x = num / value[n];
            if (x < 4) {
                for (int i = 0; i < x; ++i) res += roman[n];
            } else if (x == 4) {
                res += roman[n]; res += roman[n-1];
            } else if (x < 9) {
                res += roman[n-1];
                for (int i = 6; i <= x; ++i) res += roman[n];
            } else if (x == 9) {
                res += roman[n]; res += roman[n-2];
            }
            num %= value[n];
        }
        return res;
    }
};

方法二：贪心查表（常用且清晰）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string intToRoman(int num) {
        string res = "";
        vector<int> val{1000,900,500,400,100,90,50,40,10,9,5,4,1};
        vector<string> str{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        for (int i = 0; i < val.size(); ++i) {
            while (num >= val[i]) {
                num -= val[i];
                res += str[i];
            }
        }
        return res;
    }
};

方法三：按位查表（O(1)）

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    string intToRoman(int num) {
        vector<string> M{"","M","MM","MMM"};
        vector<string> C{"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
        vector<string> X{"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
        vector<string> I{"","I","II","III","IV","V","VI","VII","VIII","IX"};
        return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
    }
};
  • 复杂度： 三种方法均为常数时间（输入范围限制），空间 O(1)。

作者想说的话：
整数转罗马可以用按位分解或查表的思路来做：若想代码最简洁直接用按位查表；若想实现通用且直观，贪心查表是最常见的写法。