题目描述

给你一个整数，请将它转化成罗马数字。输入的整数在1到3999之间。

样例

输入：9，输出："IX"
输入：123，输出："CXXIII"

算法

(模拟) $O(logn)$

我们需要先了解罗马数字的计数方法：

1. 相同的数字连写，所表示的数等于这些数字相加得到的数，如：III=3；
2. 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如：VIII=8, XII=12；
3. 小的数字在大的数字的左边（限于 IV、IX、XL、XC、CD和CM），所表示的数等于大数减小数得到的数，如：IV=4, IX=9；
4. 正常使用时，连写的数字重复不得超过三次；

我们可以将所有减法操作看做一个整体，当成一种新的单位。从大到小整理所有单位得到：

此时我们可以将目标整数看成这些单位值的加和，且同一种单位不能使用超过3次。
所以我们尽可能优先使用值较大的单位即可。

时间复杂度分析：计算量与最终罗马数字的长度成正比，对于每一位阿拉伯数字，罗马数字最多用4个字母表示（比如VIII=8），所以罗马数字的长度和阿拉伯数字的长度是一个数量级的，而阿拉伯数字的长度是 $O(logn)$，因此时间复杂度是 $O(logn)$。

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;
    }
};