https://leetcode.com/problems/largest-number
179. Largest Number
給一個非負整數列表 nums
將它排成最大的數字並回傳它
因為數字可能很大 所以是回傳字串而不是整數
Example 1:
Input: nums = [10,2]
Output: "210"
Example 2:
Input: nums = [3,30,34,5,9]
Output: "9534330"
Constraints:
* 1 <= nums.length <= 100
* 0 <= nums[i] <= 10^9
思路：
因為要數字開頭越大越前面
原本想法很簡單 根據每個數反轉後排序
nums.sort(reverse=True, key=lambda x: str(x)[::-1])
結果馬上就錯了(
後來想說改為靠左對齊並在右邊補0
nums.sort(reverse=True, key=lambda x: str(x).ljust(len_max, '0')
過了一些但還是錯了
再研究發現並不是補0 而是要補兩數間長度差的前n位數 才會知道大小
如 8308 跟 830 差1 會比較肯定是至少1個數相同
只補1個數的話兩邊都是 8308 看不出來 要補2個數變成
8308_8 跟 830_83 所以知道 8308 放前面
最後想說乾脆逐個比對 超越不了再insert
Python Code:
class Solution:
def largestNumber(self, nums: List[int]) -> str:
if len(nums) == 1: return str(nums[0])
ans = [str(nums[0])]
for num in nums[1:]:
n = len(ans)
while n:
if f'{num}{ans[n-1]}' <= f'{ans[n-1]}{num}':
ans.insert(n, str(num))
break
n -= 1
else: # 檢查到第0個都是比較大的話 就插到最前面
ans.insert(0, str(num))
return str(int(''.join(ans))) # 有 [0,0] 這種東西 ((
想了一個早上 比預期中難 不早早早了