[LeetCode][Python]Largest Number
# -*- coding: utf8 -*-'''
__author__ = 'dabay.wang@gmail.com'
https://oj.leetcode.com/problems/largest-number/
Given a list of non negative integers, arrange them such that they form the largest number.
For example, given , the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.
===Comments by Dabay===
把所有num都存到一个hash表中，用值来记录出现的次数。
对于，num中很多重复项来说，这样的处理可以节约时间。
定义比较的方法：当两个字符串长度不一样时，把他们互相加到末尾比较。
'''
class Solution:
# @param num, a list of integers
# @return a string
def largestNumber(self, num):
def compare(num1, num2):
if len(num1) != len(num2):
num1,num2 = num1 + num2,num2 + num1
return [-1, 1]
d = {}
for n in num:
n = str(n)
if n not in d:
d = 1
else:
d = d + 1
keys = d.keys()
keys = sorted(keys, cmp=compare, reverse=True)
result = ""
for k in keys:
result = result + str(k) * d
result = result.lstrip('0')
if len(result) == 0:
return "0"
else:
return result
def main():
s = Solution()
nums =
nums =
#nums =
print s.largestNumber(nums)
if __name__ == "__main__":
import time
start = time.clock()
main()
print "%s sec" % (time.clock() - start)
页:
[1]