模拟

罗马数字和掰手指数数的区别在于，IV/IXIV/IXIV/IX 这类倒着数数的，和阿拉伯数字最大的区别在于 555 的 10k10^k10k 倍 k∈Nk\isin Nk∈N ，需要被表示出来。所以除了记录 I/X/C/MI/X/C/MI/X/C/M ——1/10/100/10001/10/100/10001/10/100/1000，还要记录 V/L/DV/L/DV/L/D——5/50/5005/50/5005/50/500 ，以及倒着数数的 IV/IX/XL/XC/CD/CMIV/IX/XL/XC/CD/CMIV/IX/XL/XC/CD/CM——4/9/40/90/400/9004/9/40/90/400/9004/9/40/90/400/900 。 类比十进制 ， 从大到小 ， 循环编码即可。

代码展示

class Solution {
public:string intToRoman(int num) {string ans="";int nums[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};string roman[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};for(int i =0;i<13;i++){while(num>=nums[i]){num-=nums[i];ans +=roman[i];}}return ans;}
};

时间复杂度 O(logn)O(logn)O(logn) ， nnn 是 numnumnum 的大小，循环编码时间复杂度 O(logn)O(logn)O(logn)。

空间复杂度 O(∣C∣)O(|C|)O(∣C∣) ， 编码的空间复杂度 O(∣C∣)O(|C|)O(∣C∣) ， ∣C∣=13|C| = 13∣C∣=13 。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC