分析

• 本题的考点：打表。

• 阿拉伯数字与罗马数字对应关系如下表：

• 我们将所有的9、5、4、1的对应关系使用数组记录下来，然后从大到小遍历这些罗马数字对应的阿拉伯数字，结果字符串中加上对应罗马字母，然后将待转换数字减去对应数据即可。例如将num = 58转为罗马数字；因为58>50，所以：res = "L", num = num-50 = 8；因为8>5，所以：res = "LV", num = num-5 = 3；因为3>1，所以：res = "LVI", num = num-1 = 2；…，最终结果res = LVIII。

代码

• C++

class Solution {
public:
    string intToRoman(int num) {

        int values[] = {
            1000,
            900, 500, 400, 100,
            90, 50, 40, 10,
            9, 5, 4, 1,
        };
        string reps[] = {
            "M",
            "CM", "D", "CD", "C",
            "XC", "L", "XL", "X",
            "IX", "V", "IV", "I",
        };

        string res;
        for (int i = 0; i < 13; i++) {
            while (num >= values[i]) {
                num -= values[i];
                res += reps[i];
            }
        }
        return res;
    }
};

• Java

class Solution {
    public String intToRoman(int num) {

        int[] values = {
            1000,
            900, 500, 400, 100,
            90, 50, 40, 10,
            9, 5, 4, 1,
        };
        String[] reps = {
            "M",
            "CM", "D", "CD", "C",
            "XC", "L", "XL", "X",
            "IX", "V", "IV", "I",
        };

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 13; i++) {
            while (num >= values[i]) {
                num -= values[i];
                sb.append(reps[i]);
            }
        }
        return sb.toString();
    }
}

时空复杂度分析

• 时间复杂度：$O(1)$。

• 空间复杂度：$O(1)$。