My step-by-step Ruby solution, beating 100% of previous in running time


  • 0
    C

    My initial idea is to sort every number in dictionary order and join them together, which result in the following ruby code:

    nums.collect{|i| i.to_s}.sort!.reverse!.join
    

    But this will fail the test case [121, 12] as "121" > "12" in dictionary order but the larger combined number should be 12121. This lead me to consider the shorter number should be preferred. Thus I add an a to the end of every number to let short one win.

    nums.collect{|i| i.to_s << 'a'}.sort!.reverse!.collect{|i| i[0..-2]}.join
    

    But this time it failed the test case [128, 12]. OK, seems that the comparison should be made against the self-duplication string. For example, to make "121" < "12" < "128", we can repeat every of them two times, and compare in dictionary order, which make "12121" < "1212" < "128128".

    nums.collect{|i| i.to_s * 2}.sort!.reverse!.collect{|i| i[0..i.length/2 - 1]}.join
    

    This time the code meet with a core case [0, 0] which the expected answer is "0" but this code will give "00". This can be solved with regular expression.

    nums.collect{|i| i.to_s * 2}.sort!.reverse!.collect{|i| i[0..i.length/2 - 1]}.join..sub(/^[0]+/,'0')
    

    Yet again, this code failed the test case [1440,7548,4240,6616,733,4712,883,8,9576], which the expected answer is "9576888375487336616471242401440" but the code get "9576883875487336616471242401440". Clearly "8" should be considered prior to "883", but "88" < "883883" in dictionary order. I solve this by repeating every number x times, where x is the max length of all numbers. This can give correct solution, but it may be possible to further optimize this solution.

    def largest_number(nums)
        nums = nums.collect{|i| i.to_s}
        max_length = nums.collect{|i| i.length}.max
        nums.collect{|i| i * max_length}.sort!.reverse!.collect{|i| i[0..i.length/max_length-1]}.join.sub(/^[0]+/,'0')
    end
    

Log in to reply
 

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