[ LeetCode ] 179. Largest Number

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

Input: [10,2]
Output: "210"

Example 2:

Input: [3,30,34,5,9]
Output: "9534330"

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

https://leetcode.com/problems/largest-number/description/



這題其實是排序問題，A+B > B+A 是關鍵。用快速排序可以很漂亮的實現演算法。


class Solution: """ @param nums: A list of non negative integers @return: A string """ def largestNumber(self, num): num = [str(x) for x in num] #num.sort(cmp=lambda x, y: cmp(y + x, x + y)) num = self.quickSort(num) largest = ''.join(num) return largest.lstrip('0') or '0' def quickSort(self, num): if len(num) < 2: return num pivot = num.pop() left = [] right = [] for i in range(len(num)): x = int(str(pivot) + str(num[i])) y = int(str(num[i]) + str(pivot)) if x < y: left.append(num[i]) else: right.append(num[i]) return self.quickSort(left) + [pivot] + self.quickSort(right)