题目描述（中等难度）

12. Integer to Roman - 图1 把数字转换成罗马数字，正常情况就是把每个字母相加，并且大字母在前，小字母在后，上边也介绍了像 4 和 9 那些特殊情况。

解法一

这个是自己的解法，主要思想就是每次取出一位，然后得到相应的罗马数字，然后合起来就行。 1. public String getRoman(int num,int count){ //count 表示当前的位数，个位，十位... 2. char[]ten={'I','X','C','M'}; //1,10,100,1000 3. char[]five={'V','L','D'};//5,50,500 4. String r=""; 5. if(num<=3){ 6. while(num!=0){ 7. r+=ten[count]; 8. num--; 9. } 10. } 11. if(num==4){ 12. r=(ten[count]+"")+(five[count]+""); 13. } 14. if(num==5){ 15. r=five[count]+""; 16. } 17. if(num>5&&num<9){ 18. r=five[count]+""; 19. num-=5; 20. while(num!=0){ 21. r+=ten[count]; 22. num--; 23. } 24. } 25. if(num==9){ 26. r = (ten[count] + "") + (ten[count + 1] + ""); 27. } 28. return r; 29. } 30. public String intToRoman(int num) { 31. String r=""; 32. int count=0; 33. while(num!=0){ 34. int pop=num%10; 35. r=getRoman(pop,count)+r; 36. count++; 37. num/=10; 38. } 39. return r; 40. }

时间复杂度：num 的位数 12. Integer to Roman - 图2 所以时间复杂度是 O（log（n））。 空间复杂度：常数个变量，O（1）。 下边在分享一些 LeetCode 讨论里的一些解法。

解法二

https://leetcode.com/problems/integer-to-roman/discuss/6310/My-java-solution-easy-to-understand 1. public String intToRoman(int num) { 2. int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1}; 3. String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"}; 4. 5. StringBuilder sb = new StringBuilder(); 6. 7. for(int i=0;i= values[i]) { 9. num -= values[i]; 10. sb.append(strs[i]); 11. } 12. } 13. return sb.toString(); 14. }

相当简洁了，主要就是把所有的组合列出来，因为罗马数字表示的大小就是把所有字母相加，所以每次 append 那个，再把对应的值减去就行了。 时间复杂度：不是很清楚，也许是 O（1）？因为似乎和问题规模没什么关系了。 空间复杂度：O（1）.

解法三

https://leetcode.com/problems/integer-to-roman/discuss/6376/Simple-JAVA-solution 1. public String intToRoman(int num) { 2. String M[] = {"", "M", "MM", "MMM"};//0,1000,2000,3000 3. String C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};//0,100,200,300... 4. String X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};//0,10,20,30... 5. String I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};//0,1,2,3... 6. return M[num/1000] + C[(num%1000)/100]+ X[(num%100)/10] + I[num%10]; 7. }

这就更加暴力了，把每位的情况都列出来然后直接返回，但思路清晰明了呀。 时间复杂度：O（1）或者说是 num 的位数，不是很确定。 空间复杂度：O（1）。

总

这道题感觉难度应该是 easy ，没有那么难，就是理清楚题意，然后就可以往出列举就行了。 windliang wechat 添加好友一起进步~ 如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^ 如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情