Source: Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example:

Given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

解題：

  1. 儘管這是一個經過排序即可解決的問題，但這邊並無法使用內建的排序功能排出我們想要的順序，無論是用str或是int型別；
  2. 那如何客製化我們想要的排序方式呢？其中一個方法就是另外設計一個class並在其中定義比較符號的判定方式。不清楚的人請詳Python官方文件或Python 研究-魔術方法指南；
  3. 知道自定義比較符號判定方法可以如何設定後後接著就是要決定如何定義比較方式了：舉例來說，此比較方式的邏輯必須符合 9 > 98 > 95555 > 890 > 8，看起來很沒邏輯？把這些數字兩兩組合在一起再做比較就會清楚許多：
    • 998 > 989
    • 9895555 > 9555598
    • 8908 > 8890

Code:


class Num:
    def __init__(self, v):
        self.val = str(v)

    def __lt__(self, other):
        return self.val + other.val < other.val + self.val

class Solution:
    # @param A : tuple of integers
    # @return a strings
    def largestNumber(self, A):
        num_list = []
        for i in A:
            num_list.append(Num(i))
        num_list.sort(reverse=True)

        output = []
        for i in num_list:
            output.append(i.val)

        if output[0][0] == '0':
            output = ['0']

        return(''.join(output))

GitHub: GitHub

發表留言