题解66 | 跑马溜溜的罗马#整数转罗马数字#

#include <utility>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串
     */
    string ArabicToRoman(int n) {
        // write code here gracefully
        string ans {};
        pair<int, string> roman[] = {
            {1000,"M"},
            {900, "CM"},//小的数字在大的数字的左边,所表示的数等于大数减小数得到的数,
            {500, "D"},
            {400, "CD"},//同理
            {100, "C"},
            {90,  "XC"},//同理
            {50,  "L"},
            {40,  "XL"},//同理
            {10,  "X"},
            {9,   "IX"},//同理
            {5,   "V"},
            {4,   "IV"},//同理
            {1,   "I"}
        };
        for (auto it : roman) {
            while (it.first <= n) {
                n -= it.first;
                ans += it.second;
            }
            if (n == 0) {
                break;
            }
        }
        return ans;
    }
};

算法基本思想：

贪心算法。将罗马数字中可能出现的所有情况和对应的阿拉伯数字存储在一个数组中，从大到小遍历数组，每次将能够表示的最大的罗马数字加入答案中，直到遍历完整个数组或者阿拉伯数字为0。

p.s.在罗马数字表示中，4、9、40、90、400、900等数字有特殊的表示方式，它们是通过在较大的罗马数字前面加上一个较小的罗马数字来表示的。这样做的原因是为了避免出现连续相同的罗马数字，这样可以使得罗马数字表示更加简洁和规范。

例如，4用"IV"表示，9用"IX"表示，40用"XL"表示，90用"XC"表示，400用"CD"表示，900用"CM"表示。这样做可以使得罗马数字表示更加紧凑，也符合罗马数字的规范表示方式。因此，在阿拉伯数字转换为罗马数字的过程中，需要考虑到这些特殊情况，从而确保得到正确的罗马数字表示。

时间复杂度：

O(13)，遍历罗马数字数组，数组长度为13。

空间复杂度：

O(1)，只需要常数级别的空间存储罗马数字数组和答案字符串。