動機

原本以為只要挑數字最大的就好…

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))