题目描述：

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.

题目大意：

给定一列非负整数，将它们以合适的顺序进行排列，使得组成的数字最大。

例如给定[3, 30, 34, 5, 9]，组成的最大数字是9534330

注意：结果可能非常大，因此你需要返回一个字符串而不是整数。

解题思路：

排序（Sort）

排序思路：对于两个备选数字a和b，如果str(a) + str(b) > str(b) + str(a)，则a在b之前，否则b在a之前

按照此原则对原数组从大到小排序即可

时间复杂度O（nlogn）

易错样例：

Input:     [0,0]
Output:    "00"
Expected:  "0"

Python代码：

class Solution:
    # @param num, a list of integers
    # @return a string
    def largestNumber(self, num):
        num = sorted([str(x) for x in num], cmp = self.compare)
        ans = ''.join(num).lstrip('0')
        return ans or '0'

    def compare(self, a, b):
        return [1, -1][a + b > b + a]

 

本文链接：http://bookshadow.com/weblog/2015/01/13/leetcode-largest-number/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码