Java Accepted Solution Using Binary Search


  • 0
    A
    private static Map<Integer, String> decimalToRomanNumerals = new HashMap<Integer, String>() {{
            put(1, "I");
            put(4, "IV");
            put(5, "V");
            put(9, "IX");
            put(10, "X");
            put(40, "XL");
            put(50, "L");
            put(90, "XC");
            put(100, "C");
            put(400, "CD");
            put(500, "D");
            put(900, "CM");
            put(1000, "M");
        }};
    
        private static int[] decimals = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
    
        public String intToRoman(final int number) {
            int decimal = number;
            StringBuffer buffer = new StringBuffer();
            while (decimal > 0) {
                // find the highest decimal value v that is less than or equal to the decimal number
                int index = Arrays.binarySearch(decimals, decimal);
                if (index < 0) {
                    // if not found then the returned index is -insertionPoint - 1.
                    // The insertionPoint is defined as the point at which the key would be inserted into the array:
                    // the index of the first element greater than the key, or a.length if all elements in the array
                    // are less than the specified key.
                    index = -(index+1); // insertionPoint+1
                    index--;    // we want the element index less than or equal to the decimal number
                }
                decimal -= decimals[index];
                buffer.append(decimalToRomanNumerals.get(decimals[index]));
            }
            return buffer.toString();
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.