動機
原本以為只要挑數字最大的就好…
Problem
Given a list of non-negative integers nums
, arrange them such that they form the largest number.
Note: The result may be very large, so you need to return a string instead of an integer.
Example 1:
Input: nums = [10,2]Output: 210
Example 2:
Input: nums = [3,30,34,5,9]Output: 9534330
Example 3:
Input: nums = [1]Output: 1
Example 4:
Input: nums = [10]Output: 10
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 109
Sol1
以[111311, 1113]
為例,如果挑最大數字,就會把111311放前面,就會出事
但[432,43243]
,就要挑最大數字
這裡的問題是,把相同的prefix去掉後,要怎麼比?
把剩下的數字,接上相同的prefix,取與另一邊一樣的長度,再去比
432,43243
=>
, 43
=>
432, "43" + "4"
=>
432,434
def com(a,b):
i = 0
j = 0
while i < len(a) and j < len(b):
if a[i] == b[j]:
i += 1
j += 1
elif a[i] > b[j]:
return 1
else:
return -1
if i >= len(a) and j >= len(b):
return 0
else:
if i >= len(a):
b = b[j:] + a[:len(b)-j-1]
else:
a = a[i:] + b[:len(a)-i-1]
return com(a,b)
class Solution:
def largestNumber(self, nums: List[int]) -> str:
nums = [str(n) for n in nums]
nums.sort(key=cmp_to_key(com), reverse=True)
ret = ""
for n in nums:
ret += n
return str(int(ret))
Sol2
如果說都要接上的話,為什麼不比較一個在前一個在後的大小就好
def com(a,b):
x, y = [a+b,b+a]
if x > y:
return 1
elif x < y:
return -1
else:
return 0
class Solution:
def largestNumber(self, nums: List[int]) -> str:
nums = [str(n) for n in nums]
nums.sort(key=cmp_to_key(com), reverse=True)
ret = ""
for n in nums:
ret += n
return str(int(ret))